Java实现字符串表达式求值

阳光穿透心脏的1/2处 2023-05-22 08:55 22阅读 0赞

## 需求说明 ##

最近在用java写一个计算器，遇到了一个问题，获取用户输入的需要计算的表达式，因为是字符串的形式所以无法进行直接计算，所以需要写一些算法来对字符串表达式进行求值。

## 实现 ##

### JS实现 ###

相信大家应该都知道JavaScript，JavaScript里面有个函数eval()可以计算某个字符串，并执行其中的JavaScript代码。虽然JavaScript名字里面有个Java，但是JavaScript和Java没什么联系的，那我上面说的这些有什么用呢？  
在JDK1.6中，我们可以使用内置的JavaScript引擎，意味着我们可以使用JavavScript里面的eval()函数。

import javax.script.ScriptEngine;
    import javax.script.ScriptEngineManager;
    import javax.script.ScriptException;
    
    public class OperationJS {
        
        public static void main(String[] args) throws ScriptException {
        
            ScriptEngineManager mgr = new ScriptEngineManager();
            ScriptEngine engine = mgr.getEngineByName("JavaScript");
            String foo = "(40+2)*2";
            System.out.println(engine.eval(foo));
        }
    }

使用这个要注意一个安全问题，执行的JavaScript可以访问所有Java类，因此可以无限制地劫持您的应用程序。  
例如下面这句代码，将通过JavaScript将文件写入（默认情况下）程序的当前目录

engine.eval("var f = new java.io.FileWriter('hello.txt'); f.write('hello!'); f.close();");

发现这个有点方便。秉着学习的原则，出现了实现二，用算法来解决。

### 栈实现 ###

#### 基本分析 ####

*  表达式主要有括号和加减乘除四种基本运算。表达式可以看成是由一个个二元运算组成，前一个二元运算可以作为后一个二元运算的输入。  
    例如：“1+2+3”，可以看成是两个二元运算组成(1+2)+3，前一个二元运算过后就变成3+3，这又是一个二元运算，最后结果为6。既然都是二元运算计算，我们就可以用同一段程序来解决，递归或循环。但是我们要注意加减乘除有优先级之分。
 *  加减乘除四种运算符是有优先级的，乘法或除法同级，且比加法或减法优先级高。优先级的出现对程序的设计影响很大，例如：”1+2+3-4“=“3+3-4”=“6-4”=2，如果整个表达式都是同级的我们就可以直接从头一直运算到尾。但是因为有优先级的出现我们就不可以这样做，例如：“1+2\*3-4”=“1+6-4”=“3”,我们需要先算在表达式中间的”2\*3“，而不能从头的"1+2"开始算。优先级的出现让程序变的复杂了起来。
 *  括号的处理，括号就相当于在表达式里面嵌套了一个子表达式，而子表达式的优先级比括号外的其他运算优先级高。

分析可得，表达式有两个基本元素，操作数和运算符。

#### 算法思想 ####

*  操作数栈：解析表达式，采用逐个读取字符的形式，如果是操作数就入操作数栈，需要注意的是，我们是逐个读取字符，也就意味着数字"123"将分3次读取(“1”,“2”,“3”)，所以需要一个追加器将字符缓存起来，当完整的读取了整个数值时在入操作数栈。
 *  运算符栈：如果是运算符就进行比较，优先级同级或低于栈顶运算符时，将触发一次二元运算，进行二元运算的为运算符栈的栈顶元素和操作数栈顶的两个元素，再把运算得到的结果入操作数栈。如果运算栈还有元素，这是一个递归操作，直到运算栈没有元素或者运算符的优先级高于栈顶元素，那么把运算符入运算符栈。继续读取表达式的下一个元素。  
    例如：”1+2\*3-4“。  
    如下图所示，(6)在读取"-“时，优先级低于栈顶运算符”*"，触发二元运算，取出操作数栈顶元素"3"和"2"与运算符栈顶元素"*“进行一次二元运算"2\*3”=“6”，得到结果"6"，把运算出来的结果"6"入操作数栈(6.1所示)。栈顶还有元素，继续比较，栈顶元素”+“和"-“同级，再触发二元运算，取出操作数栈顶元素"6"和"1"与运算符栈顶元素”+“进行一次二元运算"1+6”=“7”，得到结果"7"，把运算出来的结果"7"入操作数栈(6.2所示)。此时运算符栈没有元素，运算符"-“入运算符栈(6.3所示)。读取下一个字符"4”，表达式已读取完毕，此时进行二元运算，直到运算符栈没有运算符，此时操作栈唯一的元素就是最后表达式计算的结果"3"(8所示)。  
    ![1+2\*3-4][1_2_3-4]
 *  括号运算：相当于子表达式运算，当读取表达式字符时，读取到"(“左括号，将左括号入运算符栈，当读取到”)"右括号时，将一直运算整个子表达式的二元运算，直到遇到左括号时停止，此时把子表达式的结果入操作数栈。加减乘除左括号右括号中左括号的优先级最低，右括号的优先级最高。  
    例如：“1+2\*(3+4)”  
    ![1+2\*(3+4)][1_2_3_4]

#### 代码实现 ####

import java.math.BigDecimal;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Stack;
    
    /**
     * 对表达式求值，支持加减乘除括号小数点，不支持负数
     */
    public class Operation {
        
        //优先级Map
        private static final Map<String,Integer> OP_PRIORITY_MAP=new HashMap<String, Integer>(){
        
            {
        
                put("(",0);
                put("+",3);
                put("-",3);
                put("*",4);
                put("/",4);
                put(")",10);
            }
        };
    
        public double operationExpression(String expression){
        
            Stack<String> opStack = new Stack<String>();         //运算符栈
            Stack<BigDecimal> numStack = new Stack<BigDecimal>();       //操作数栈
            StringBuilder numBuilder = new StringBuilder();     //当前数值的追加器
    
            for (int i = 0;i < expression.length();i++){
        
                char c = expression.charAt(i);
                if (c >= '0' && c <= '9' || c == '.'){
                  //如果是数值则加入追加器
                    numBuilder.append(c);
                }else{
                                                  //如果是运算符
                    if (numBuilder.length() > 0){
                       //如果numBuilder有值说明里面已经有一个数值
                        numStack.push(new BigDecimal(numBuilder.toString()));     //把数值入运算符栈
                        numBuilder.delete(0,numBuilder.length());  //清空数值
                    }
                    //读取到的字符是运算符
                    String op = String.valueOf(c);
                    if (opStack.empty()){
            //如果操作数栈没有运算符
                        opStack.push(op);
                    }else{
        
                        //如果是"("则直接入运算栈
                        if ("(".equals(op)){
        
                            opStack.push(op);
                        }else if (")".equals(op)){
        
                            //如果是")"则进行括号匹配运算括号内的表达式
                            while (!"(".equals(opStack.peek())){
        
                                stackOperation(opStack,numStack);
                            }
                            opStack.pop();
                        }else{
        
                            //如果是运算符，需要对比当前运算符op和栈顶的运算符优先级。
                            do {
        
                                //比较当前运算符和栈顶运算符的优先级,如果nowOp和opStack栈顶元素相同或者低级，
                                // 则进行运算，直到nowOp高于opStack栈顶
                                if (jubgmentPriority(op,opStack.peek())){
        
                                    stackOperation(opStack,numStack);
                                    if (opStack.empty()){
        
                                        opStack.push(op);
                                        break;
                                    }
                                }else {
        
                                    opStack.push(op);
                                    break;
                                }
                            }while (!opStack.empty());
                        }
                    }
                }
            }
    
            //表达式结束，追加器里面有值
            if (numBuilder.length()>0){
        
                numStack.push(new BigDecimal(numBuilder.toString()));
            }
    
            while (!opStack.empty()){
        
                stackOperation(opStack,numStack);
            }
            return numStack.pop().doubleValue();
        }
    
        /**
         * 进行一次二元运算
         * @param opStack
         * @param numStack
         */
        public void stackOperation(Stack<String> opStack,Stack<BigDecimal> numStack){
        
            String opT = opStack.pop();              //栈顶运算符
            BigDecimal num2 = numStack.pop();       //第二个操作数
            BigDecimal num1 = numStack.pop();       //第一个操作数
            BigDecimal operationNum = oneOperation(opT,num1,num2);   //num1 op num2
    
            numStack.push(operationNum);            //把计算完的结果放入操作数栈
        }
    
    
    //
    
        /**
         * 单次计算，计算为num1 op num2
         * @param op    运算符
         * @param num1  第一个操作数
         * @param num2  第二个操作数
         * @return  num1 op num2
         */
        public BigDecimal oneOperation(String op,BigDecimal num1,BigDecimal num2){
        
            BigDecimal result = new BigDecimal(0);
            switch (op){
        
                case "+":
                    result = num1.add(num2);
                    break;
                case "-":
                    result = num1.subtract(num2);
                    break;
                case "*":
                    result = num1.multiply(num2);
                    break;
                case "/":
                    result = num1.divide(num2);
                    break;
                default:
                    break;
            }
            return result;
        }
    
    
        /**
         * 比较运算符优先级
         * @param op1
         * @param op2
         * @return op1比op2相同或低级则返回true，op1比op2高级则返回false
         */
        private boolean jubgmentPriority(String op1, String op2){
        
            return (OP_PRIORITY_MAP.get(op1) - OP_PRIORITY_MAP.get(op2)) <= 0;
        }
    
        public static void main(String[] args) {
        
            Operation operation = new Operation();
            System.out.println(operation.operationExpression("(2+2)*3+3+3/3+2.2"));
        }

[1_2_3-4]: /images/20230521/718972cd9f5847779ca716cba6c25a19.png
[1_2_3_4]: /images/20230521/ca1798b743d64623a071926df2235a78.png