如何使用栈在一次扫描中评估中缀表达式？

Question

我想知道是否有一种方法可以使用两个栈在单次遍历中解决中缀表达式？

这些栈可以一个用于操作符，另一个用于运算元...

通过逆波兰算法的标准方法是将中缀表达式转换为后缀表达式（逆波兰表示法），然后再求解。我不想先将表达式转换为后缀表达式。

如果表达式类似于2*3-(6+5)+8，应该如何求解？

- nikoo28

Answer 1

虽然有点晚，但这就是答案。

使用两个栈：

1. 运算符栈 { 用于存放运算符和括号 }。
2. 操作数栈。

算法

如果存在字符需要读取：

1. 如果字符是 操作数，则将其推入 操作数栈；如果字符是 (，则将其推入 运算符栈。
2. 否则，如果字符是 运算符：
   1. 只要 运算符栈 的顶部优先级不低于此字符，就执行以下步骤。
   2. 从 运算符栈 中弹出 运算符。
   3. 从 操作数栈 中弹出两个 操作数 (op1 和 op2)。
   4. 将 op1 op op2 存储在 操作数栈 上，回到 2.1 步骤。
3. 否则，如果字符是 )，则执行与 2.2 - 2.4 相同的操作，直到遇到 (。

否则（没有更多字符需要读取）：

• 弹出运算符，直到 运算符栈 不为空。
• 从顶部弹出 2 个 操作数，并将 op1 op op2 推入 操作数栈。

从 操作数栈 返回顶部值。

- Rohit

---

“做与2相同的事情，直到遇到 ')' 为止。”

• 我相信应该是 '(' 而不是 ')'！（我的算法中的这个打字错误引起了一些头痛！！）

- Gyfis

@EJP之前从未听说过Shunting-yard算法。这个算法是我自己想出来的，但也可能迪杰斯特拉在我之前就想出来了。如果不是这样，我本来会这样做的...与其先问我并在确认后给出-1，我挑战你证明我不能完全自主地想出这个算法，而这段文字又是改编或抄袭的。如果是这样，我很乐意做必要的更改。谢谢。 - Rohit

哇，给那个东西打-1分简直太过分了。 - damianesteban

Djikstra是一位伟大的科学家，但我认为学生们可以想出这个算法，特别是给了使用两个栈的提示。 - Neo M Hacker

对于任何感兴趣的人，第一步应该是：“1. 如果字符是操作数或（。将其推入堆栈：如果是操作数，则将其推入操作数堆栈；如果是（则将其推入运算符堆栈。” - corporateAbaper

Answer 2

在这个链接中提供的方法非常好。

让我引用一下源文：

We will use two stacks:

Operand stack: to keep values (numbers)  and

Operator stack: to keep operators (+, -, *, . and ^).  


In the following, “process” means, (i) pop operand stack once (value1) (ii) pop operator stack once (operator) (iii) pop operand stack again (value2) (iv) compute value1 operator  value2 (v) push the value obtained in operand stack.          


Algorithm:


Until the end of the expression is reached, get one character and perform only one of the steps (a) through (f):

(a) If the character is an operand, push it onto the operand stack.

(b) If the character is an operator, and the operator stack is empty then push it onto the operator stack.

(c) If the character is an operator and the operator stack is not empty, and the character's precedence is greater than the precedence of the stack top of operator stack, then push the character onto the operator stack.

(d) If the character is "(", then push it onto operator stack.

(e) If the character is ")", then "process" as explained above until the corresponding "(" is encountered in operator stack.  At this stage POP the operator stack and ignore "(."

(f) If cases (a), (b), (c), (d) and (e) do not apply, then process as explained above.



 When there are no more input characters, keep processing until the operator stack becomes empty.  The values left in the operand stack is the final result of the expression.

我希望这能对您有所帮助！

- skrtbhtngr

---

很好，除了在“process”步骤中操作数的顺序被交换了--你首先弹出operand2，然后是operand1，然后计算operand1 operator operand2... - Chris Dodd

Answer 3

以下是我在Java中进行中缀表达式评估的尝试。如果您发现任何错误，请告诉我：）

import java.util.*;

public class ArithmeticExpressionEvaluation {

    public static void main(String[] args) {
        Scanner readExpression = new Scanner(System.in);
        System.out.print("Enter the expression: ");
        String expression = readExpression.nextLine();
        System.out.println(expression);
        System.out.println("Result: " + calculateExpression(expression));
    }

    public static long calculateExpression(String expression) {

        Stack<Long> operandStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();

        if (!isValidExpression(expression)) {
            System.out.println("Not a valid expression to evaluate");
            return 0;
        }

        int i = 0;
        String currentInteger = null;
        while (i < expression.length()) {

            // System.out.println(expression.charAt(i));
            if (expression.charAt(i) >= '0' && expression.charAt(i) <= '9') {

                currentInteger = expression.charAt(i) + "";
                i++;
                while (i != expression.length() && (expression.charAt(i) >= '0' && expression.charAt(i) <= '9')) {
                    currentInteger = currentInteger + expression.charAt(i);
                    i++;
                }

                operandStack.push(Long.parseLong(currentInteger));
            } else {

                if (expression.charAt(i) == ')') {

                    while (operatorStack.peek() != '(') {
                        performArithmeticOperation(operandStack, operatorStack);
                    }
                    operatorStack.pop();
                } else {

                    Character currentOperator = expression.charAt(i);
                    Character lastOperator = (operatorStack.isEmpty() ? null : operatorStack.peek());


                    if (lastOperator != null && checkPrecedence(currentOperator, lastOperator)) {
                        performArithmeticOperation(operandStack, operatorStack);
                    }
                    operatorStack.push(expression.charAt(i));

                }
                i++;
            }

        }


        while (!operatorStack.isEmpty()) {
            performArithmeticOperation(operandStack, operatorStack);
        }

    //    System.out.println(Arrays.toString(operandStack.toArray()));
    //    System.out.println(Arrays.toString(operatorStack.toArray()));

        return operandStack.pop();

    }

    public static void performArithmeticOperation(Stack<Long> operandStack, Stack<Character> operatorStack) {
        try {
            long value1 = operandStack.pop();
            long value2 = operandStack.pop();
            char operator = operatorStack.pop();

            long intermediateResult = arithmeticOperation(value1, value2, operator);
            operandStack.push(intermediateResult);
        } catch (EmptyStackException e) {
            System.out.println("Not a valid expression to evaluate");
            throw e;
        }
    }


    public static boolean checkPrecedence(Character operator1, Character operator2) {

        List<Character> precedenceList = new ArrayList<>();
        precedenceList.add('(');
        precedenceList.add(')');
        precedenceList.add('/');
        precedenceList.add('*');
        precedenceList.add('%');
        precedenceList.add('+');
        precedenceList.add('-');


        if(operator2 == '(' ){
            return false;
        }

        if (precedenceList.indexOf(operator1) > precedenceList.indexOf(operator2)) {
            return true;
        } else {
            return false;
        }

    }

    public static long arithmeticOperation(long value2, long value1, Character operator) {

        long result;

        switch (operator) {

            case '+':
                result = value1 + value2;
                break;

            case '-':
                result = value1 - value2;
                break;

            case '*':
                result = value1 * value2;
                break;

            case '/':
                result = value1 / value2;
                break;

            case '%':
                result = value1 % value2;
                break;

            default:
                result = value1 + value2;


        }
        return result;
    }


    public static boolean isValidExpression(String expression) {

        if ((!Character.isDigit(expression.charAt(0)) && !(expression.charAt(0) == '('))
                || (!Character.isDigit(expression.charAt(expression.length() - 1)) && !(expression.charAt(expression.length() - 1) == ')'))) {
            return false;
        }

        HashSet<Character> validCharactersSet = new HashSet<>();
        validCharactersSet.add('*');
        validCharactersSet.add('+');
        validCharactersSet.add('-');
        validCharactersSet.add('/');
        validCharactersSet.add('%');
        validCharactersSet.add('(');
        validCharactersSet.add(')');

        Stack<Character> validParenthesisCheck = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {

            if (!Character.isDigit(expression.charAt(i)) && !validCharactersSet.contains(expression.charAt(i))) {
                return false;
            }

            if (expression.charAt(i) == '(') {
                validParenthesisCheck.push(expression.charAt(i));
            }

            if (expression.charAt(i) == ')') {

                if (validParenthesisCheck.isEmpty()) {
                    return false;
                }
                validParenthesisCheck.pop();
            }
        }

        if (validParenthesisCheck.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

- learner

---

2+3(4*3) 的输出结果是 15。请再检查一次。 - Stunner

Answer 4

1. 创建一个空的操作符栈。
2. 创建一个空的操作数栈。
3. 对于输入字符串中的每个标记
   a. 获取中缀字符串中的下一个标记。
   b. 如果下一个标记是一个操作数，则将其放入操作数栈中。
   c. 如果下一个标记是一个运算符
   • 计算该运算符。
4. 当操作符栈不为空时，弹出操作符和操作数（左右），计算左操作符右侧并将结果推送到操作数栈中。
5. 从操作符栈中弹出结果。

- nikhil

---

这里没有提到运算符优先级。 - user207421

Answer 5

---- 这是针对没有括号的表达式 ----

仅适用于具有2个运算符的基本表达式

创建一个空的运算符栈 创建一个空的操作数栈 从字符串表达式中创建一个字符数组 对于每个字符 4.1 如果它是一个数字 将它添加到操作数栈中 4.2 如果它是一个运算符 当运算符栈为空，且当前运算符的优先级小于运算符栈顶的运算符时 { 弹出一个操作数 (v1) 弹出第二个操作数 (v2) 弹出一个运算符 (p) 计算 v2 p v1 （最先被推入的数字将最后被弹出） 将结果压入操作数栈中 } 如果运算符栈为空，则将运算符添加到栈中 在读取完所有字符之后 5.1 当运算符栈不为空时 同4.2中描述的循环过程 返回最终结果

- Lord Thanos