当前位置：首页 > article >正文

我记不住的那些表达式求值

article 2024/10/24 17:57:00

背景：

最近遇到了一个问题表达式求值，其实就是给定一个算式字符串，程序对其进行计算，最后输出结果，整个过程类似人类计算或计算器计算，一开始觉得这个问题不困难，但真正实践后发现还是有很多需要注意的地方，这里记录一下。

一、提出问题

LeetCode 224/227/772 基础计算器共3道题，前两道题是免费，最后一道是付费。

前两道题的介绍这里略过，最后一道我查阅了一下资料，如下图所示：

这三道题的差异：

这三道题的前提是给定的字符串都是有效的，也就是说能计算出最终结果的字符串。

224：字符串包括数字、'+'、'-'、'('、')'、' ' ，'+'不能作为一元运算符，'-'能作为一元运算符，结果是有符号32位整数。

即 1-( -2) 和 -(2 + 3)也是有效的，正确的字符串

227：字符串包括数字、'+'、'-'、'*'、'/'、' ', 整数都是非负的32位有符号整数(即对于'-'没有一元运算符，范围是0-2^31-1，使用int能进行承装这些数字)，结果是有符号32位整数。

772：字符串包括数字、'+'、'-'、'*'、'/'、' '、'('、')'，整数都是非负的32位有符号整数(即对于'-'没有一元运算符，范围是0-2^31-1，使用int能进行承装这些数字)，中间的结果也是32位有符号整数，结果是有符号32位整数[-2^31,2^31-1]

整体来说 224是能对一元运算符进行处理，但是操作符的数量少。而772是操作符的数量最多，但不对一元运算符进行处理。 772只是比227新增了对括号()的处理。

还有就是有哪些语言内建了eval()方法可以进行求值？

JavaScript内建了eval()，使用浏览器打开"开发者工具"在console中输入即可，例如：

eval(-2+3+10%3+3/2+(4+2)*5+Math.abs(-5))

其余语言可以查看参考资料4

二、分析问题

1. 表达式一般分为几种？

波兰表示法(前缀表示法)，即polish notation或prefix notation

正常表示法(中缀表示法)，即infix notation , leetcode224/227/772都是这种表达式，人类能看懂的表达式

逆波兰表示法(后缀表示法)，即reverse polish notation或postfix notation ,leetcode150就是这种表达式。

我们今天仅仅讨论正常表示法(中缀表示法)和逆波兰表示法(后缀表示法)的处理和计算

2. 如何确认一个表达式字符串是有效的？

例如只存在操作符的字符串是无效的，无法计算出值，或者左括号和右括号不匹配以及数量不匹配等。这个问题在LeetCode中有前提是一个合法有效的字符串，但是现实中可能输入一个无效的字符串。

3. 如何将一个表达式字符串进行识别并分拆成各个部分，例如数字、操作符、空格、括号等等？

4. 如何去掉表达式字符串中的空格？

5. 如何对'-'操作符新增一元运算符处理，即LeetCode224那种情况，还有'+'操作符作为一元操作符。

为防止 () 内出现的首个字符为运算符，将 (-x 替换为 (0-x (+x 替换为 (0+x 这样进行转换。

如果字符串为 +2+5+7或者 -2+5+7，为了减少边界判断，可以是先添加一个0到操作数栈。

6. 如何新增其他操作符，例如： %取余和 ^指数

将新增操作符添加到代码中，并新增操作符的优先级

7. int整型的数字，可能存在中间结果或最终结果的溢出，如何对溢出进行处理？

例如：全是加法，a+b+c+d+e....+...，中间结果和最终结果可能超出了2^31-1的范围。

或全是减法，-a-b-c-d-e... -...，中间结果和最终结果可能超出了-2^31的范围。

8. 如何对除0这种情况进行监测，如出现则返回错误？

三、解决问题

针对LeetCode224/227/772请各位同学去LeetCode网站查看相关的题解。

对于LeetCode未解决或者没有前提条件的问题，在这里进行解决。

0. 前导知识

正常表达式(infix notation)求值算法：

Algorithm to evaluate an Infix Expression involving non-negative operands:

1. Have two stack, one for storing operators, and another one for storing operands.
2. Iterate over the expression from left to right.
3. While iterating over the expression if you encounter anything other than valid operands and operators (including opening brace and closing brace), ignore them. This step does not apply if the expression is already sanitized to make sure the expression is valid and only valid characters exists in the expression.

4. While iterating, if you get an operand, just push it in the operand stack.
5. While iterating over the expression, if you encounter an operator (say, op1):
if the operator stack is empty or if the precedence of the operator (op1) is greater than the operator on the top of the operator stack, then just push the operator in the operator stack.
it gets interesting if the operator we encounter has a precedence less than or equal to the precedence of the operator that is at the top of the operator stack.
In this case, we need to evaluate the expression first, starting from the last operand encountered, in backward, till we either find a opening brace '(' or an operator which has precedence lower than or equal to the operator op1. To achieve this we need to follow the below three steps.
Pop top two operands from the operands stack and pop the top operator from the operator stack and process them, by process I mean calculate the value you get by operating the operator on the two operands. For example, if the first popped operand is 3 and the second popped operand is 6 and the operator is '/', then do the operation <second popped operand> <ltoperator> <second popped operand>. In our case it would be 6 / 3
Now push the value you got in the above step in the operands stack. In our case push 2 in the operands stack. We got 2 from the operation 6 / 3.
Repeat the above 2 steps, till we encounter opening brace '(' or an operator with precedence equal to less than the operator op1.
It is important to note, why we are doing the above two steps
even when the precedence is same
. The short answer is
because of ASSOCIATIVITY.

Consider the expression 6 - 3 - 2.
This expression can have two answers (of course, one of them is not correct) depending on how we calculate it.
We get the calculated value as 5 if we calculate the expression in the following way: 6 - (3 - 2). But is this correct? No.
We get the correct answer if we calculate 6 - 3 - 2 as (6 - 3) - 2 and we get 1.

So what we can conclude here is
we need to process (calculate) from left to right if the precedence of the operators are the same.


A little more on this: Addition (+) and Multiplication (*) operators are Associative. If an expression has all associative operators with same precedence, it does not matter in which order you process them you will get the same answer.
3 + 4 + 5 = (3 + 4) + 5 = 3 + (4 + 5) = 12
3 * 4 * 5 = (3 * 4) * 5 = 3 * (4 * 5) = 60.



Now that we have visited all the characters in the expression and put them in the stack and done any operations necessary, we need to process the operands and operators present in the two stack.

Important to notice that: for whatever we have left in the two stacks now, NON-ASSOCIATIVITY does not matter right now, what I mean by this you would get same calculated value irrespective of you process the left-over expression we have right now from left to right or right to left.


To do this,
Pop the top two operands and pop the operators stack, process and put the result in the operands stack.
Repeat till the operators stack is empty.

从正常表达式转化为逆波兰表达式的算法：

在1961年11月由迪杰斯特拉提出，使用的调度场算法Shunting_yard_algorithm，这个算法类似于火车的基础设施，用于多条铁路线路先后会让或由于列车调头等特殊目的所兴建。这个算法基于两个栈进行实现。

调度场算法如下，具体代码实现请STFW：

/* The functions referred to in this algorithm are simple single argument functions such as sine, inverse or factorial. */
/* This implementation does not implement composite functions, functions with a variable number of arguments, or unary operators. */

while there are tokens to be read:
    read a token
    if the token is:
    - a number:
        put it into the output queue
    - a function:
        push it onto the operator stack 
    - an operator o1:
        while (
            there is an operator o2 at the top of the operator stack which is not a left parenthesis, 
            and (o2 has greater precedence than o1 or (o1 and o2 have the same precedence and o1 is left-associative))
        ):
            pop o2 from the operator stack into the output queue
        push o1 onto the operator stack
    - a ",":
        while the operator at the top of the operator stack is not a left parenthesis:
             pop the operator from the operator stack into the output queue
    - a left parenthesis (i.e. "("):
        push it onto the operator stack
    - a right parenthesis (i.e. ")"):
        while the operator at the top of the operator stack is not a left parenthesis:
            {assert the operator stack is not empty}
            /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
            pop the operator from the operator stack into the output queue
        {assert there is a left parenthesis at the top of the operator stack}
        pop the left parenthesis from the operator stack and discard it
        if there is a function token at the top of the operator stack, then:
            pop the function from the operator stack into the output queue
/* After the while loop, pop the remaining items from the operator stack into the output queue. */
while there are tokens on the operator stack:
    /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
    {assert the operator on top of the stack is not a (left) parenthesis}
    pop the operator from the operator stack onto the output queue

1. 直接求正常表达式infix notation的值

分为递归法和迭代法

递归法可以参考 PA1中的表达式求值 · GitBook ，这种方法将一个正常表达式进行分隔为多个正常表达式，再分别求值，最后汇总。采用了分治法、系统栈、递归进行了解答，为了学术诚信 (Academic Integrity)，这里不贴代码了。

迭代法可以参考，这种方法采用了按照顺序依次处理、两个额外的栈进行了处理，如果使用Java语言可以使用Deque实现两个栈，如果是C语言可以使用数组或链表实现一个栈

public int evaluateInfixExpression(String expression) throws Exception {

    Deque<Integer> operands = new ArrayDeque<>();
    Deque<Character> operators = new ArrayDeque<>();

    char[] ch = expression.toCharArray();

    for(int i = 0; i < ch.length; i++) {
        char c = ch[i];

        if(Character.isDigit(c)){
            //operands can be one or more digits long
            int num = 0;
            while (i < ch.length && Character.isDigit(ch[i])) {
                num = num * 10 + (ch[i] - '0');
                i++;
            }
            i--;
            operands.push(num);
        }
        else if( c == '('){
            operators.push(c);
        }
        else if(c == ')') {
            // calculate the whole expression surrounded by the closing and corresponding braces
            while(operators.peek() != '('){
                int ans = calculate(operands, operators);
                operands.push(ans);
            }
            operators.pop();
        }
        else if(isOperator(c)){
            while(!operators.isEmpty() && precedence(c) <= precedence(operators.peek())){
                int ans = calculate(operands, operators);
                operands.push(ans);
            }
            operators.push(c);
        }
    }

    // all the characters in the expression have been visited and put on the stack
    // with some operations done whenever necessary.
    // Now just calculate everything you have in stack
    while(!operators.isEmpty()){
        int ans = calculate(operands, operators);
        operands.push(ans);
    }
    return operands.pop();
}

private boolean isOperator(char c) {
    return (c=='+'||c=='-'||c=='/'||c=='*'||c=='^');
}

private int precedence(char c) {
    switch (c){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
    }
    return -1;
}

private int calculate(Deque<Integer> operands, Deque<Character> operators) throws Exception {

    int a = operands.pop();
    int b = operands.pop();

    char operator = operators.pop();

    switch (operator) {
        case '+':
            return a + b;
        case '-':
            return b - a; // not a - b since evaluation is done from left to right.
        case '*':
            return a * b;
        case '^':
            return  (int) Math.pow(b, a);
        case '/':
            if (a == 0) {
                throw new Exception("Cannot divide by zero");
            }
            return b / a; // not a / b since evaluation is done from left to right.
    }
    return 0;
}