顺序栈实现算术表达式的计算

顺序栈可以用来实现算术表达式的计算。具体实现思路如下：
1. 定义两个栈，stack0用于存储操作数，stack1用于存储操作符。
2. 从左往右扫描表达式，遇到操作数则入栈stack0。
3. 遇到操作符时，如果优先级低于或等于栈顶操作符优先级，则从stack1弹出一个操作符和两个操作数进行计算，并将结果压入stack0。
4. 如果优先级高于栈顶操作符优先级，则将操作符入栈stack1。
5. 当表达式扫描完毕后，如果stack1不为空，则从stack1弹出一个操作符和两个操作数进行计算，并将结果压入stack0。
6. 最终stack0中只剩下一个元素，即为表达式的计算结果。

举个例子，假设要计算表达式"3+4*5-6"，则按照上述步骤进行计算：
1. 遇到3，入栈stack0。
2. 遇到+，入栈stack1。
3. 遇到4，入栈stack0。
4. 遇到*，入栈stack1。
5. 遇到5，入栈stack0。
6. 此时栈顶操作符为*，优先级高于+，因此不进行计算，将*入栈stack1。
7. 遇到-，入栈stack1。
8. 遇到6，入栈stack0。
9. 此时表达式扫描完毕，stack1中还剩下*和-两个操作符，因此先计算*，得到20，再计算-，得到17，最终结果为17。

相关问题

顺序栈实现算术表达式

顺序栈可以用来实现算术表达式的计算。具体实现方法如下：

1. 定义一个栈，用于存储操作数和运算符。
2. 从左到右扫描表达式，遇到操作数则入栈，遇到运算符则将栈顶的两个操作数出栈进行运算，并将结果入栈。
3. 最终栈中只剩下一个元素，即为表达式的计算结果。

以下是一个示例代码：

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
def calculate(expression):
    stack = Stack()
    for char in expression:
        if char.isdigit():
            stack.push(int(char))
        else:
            num2 = stack.pop()
            num1 = stack.pop()
            if char == '+':
                stack.push(num1 + num2)
            elif char == '-':
                stack.push(num1 - num2)
            elif char == '*':
                stack.push(num1 * num2)
            elif char == '/':
                stack.push(num1 / num2)
    return stack.pop()

expression = '3+4*5-6/2'
result = calculate(expression)
print(result) # 输出 20.0

用栈实现算术表达式的求解

算法思路：

1.定义两个栈，一个存储操作数，一个存储操作符。

2.遍历算术表达式，依次进行以下操作：

①如果遇到数字，将其入操作数栈。

②如果遇到左括号，将其入操作符栈。

③如果遇到右括号，则进行括号内的计算，直到遇到左括号，将左括号出栈。

④如果遇到加、减、乘、除等操作符，则将操作符入操作符栈。

⑤如果遍历完整个表达式，操作符栈中还有运算符，就按顺序进行计算，直到操作符栈为空。

3.最后操作数栈中只剩下一个元素，即为表达式的结果。

算法实现：

public static int evaluateExpression(String expression) {
    Stack<Integer> operandStack = new Stack<>();
    Stack<Character> operatorStack = new Stack<>();
    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);
        if (c >= '0' && c <= '9') {
            operandStack.push(c - '0');
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!operatorStack.isEmpty() && priority(c) <= priority(operatorStack.peek())) {
                int num2 = operandStack.pop();
                int num1 = operandStack.pop();
                char operator = operatorStack.pop();
                operandStack.push(applyOperator(num1, num2, operator));
            }
            operatorStack.push(c);
        } else if (c == '(') {
            operatorStack.push(c);
        } else if (c == ')') {
            while (operatorStack.peek() != '(') {
                int num2 = operandStack.pop();
                int num1 = operandStack.pop();
                char operator = operatorStack.pop();
                operandStack.push(applyOperator(num1, num2, operator));
            }
            operatorStack.pop();
        }
    }
    while (!operatorStack.isEmpty()) {
        int num2 = operandStack.pop();
        int num1 = operandStack.pop();
        char operator = operatorStack.pop();
        operandStack.push(applyOperator(num1, num2, operator));
    }
    return operandStack.pop();
}

private static int applyOperator(int num1, int num2, char operator) {
    switch (operator) {
        case '+':
            return num1 + num2;
        case '-':
            return num1 - num2;
        case '*':
            return num1 * num2;
        case '/':
            return num1 / num2;
        default:
            return 0;
    }
}

private static int priority(char operator) {
    switch (operator) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

算法时间复杂度：O(n)。

算法空间复杂度：O(n)。