题解 | #表达式求值#

解题思路

这是一个基本的计算器实现，需要处理以下内容：
- 支持加减乘除运算（+, -, *, /）
- 支持括号运算
- 支持多位数字
- 表达式长度不超过100
- 所有数值在int范围内（ $-2^{31} \leq val \leq 2^{31} - 1$ ）
实现思路：
- 使用两个栈：一个存储数字，一个存储运算符
- 遇到数字直接入栈
- 遇到运算符需要比较优先级
- 遇到左括号直接入栈
- 遇到右括号需要计算到左括号为止

代码

c++
java
python

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 判断运算符优先级
int priority(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

// 执行运算
int calculate(int a, int b, char op) {
    switch(op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: return 0;
    }
}

int main() {
    string s;
    while (getline(cin, s)) {
        stack<int> nums;
        stack<char> ops;
        
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ' ') continue;
            
            // 处理负数
            if (s[i] == '-' && (i == 0 || s[i-1] == '(' || s[i-1] == '+' || s[i-1] == '-' || s[i-1] == '*' || s[i-1] == '/')) {
                nums.push(0);  // 在负数前添加0
            }
            
            if (isdigit(s[i])) {
                int num = 0;
                while (i < s.length() && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                i--;
                nums.push(num);
            }
            else if (s[i] == '(') {
                ops.push(s[i]);
            }
            else if (s[i] == ')') {
                while (!ops.empty() && ops.top() != '(') {
                    int b = nums.top(); nums.pop();
                    int a = nums.top(); nums.pop();
                    char op = ops.top(); ops.pop();
                    nums.push(calculate(a, b, op));
                }
                ops.pop(); // 弹出左括号
            }
            else { // 运算符
                while (!ops.empty() && ops.top() != '(' && 
                       priority(ops.top()) >= priority(s[i])) {
                    int b = nums.top(); nums.pop();
                    int a = nums.top(); nums.pop();
                    char op = ops.top(); ops.pop();
                    nums.push(calculate(a, b, op));
                }
                ops.push(s[i]);
            }
        }
        
        while (!ops.empty()) {
            int b = nums.top(); nums.pop();
            int a = nums.top(); nums.pop();
            char op = ops.top(); ops.pop();
            nums.push(calculate(a, b, op));
        }
        
        cout << nums.top() << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    // 判断运算符优先级
    private static int priority(char op) {
        if (op == '*' || op == '/') return 2;
        if (op == '+' || op == '-') return 1;
        return 0;
    }
    
    // 执行运算
    private static int calculate(int a, int b, char op) {
        switch(op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
            default: return 0;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            Stack<Integer> nums = new Stack<>();
            Stack<Character> ops = new Stack<>();
            
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == ' ') continue;
                
                // 处理负数
                if (s.charAt(i) == '-' && (i == 0 || s.charAt(i-1) == '(' || s.charAt(i-1) == '+' || s.charAt(i-1) == '-' || s.charAt(i-1) == '*' || s.charAt(i-1) == '/')) {
                    nums.push(0);  // 在负数前添加0
                }
                
                if (Character.isDigit(s.charAt(i))) {
                    int num = 0;
                    while (i < s.length() && Character.isDigit(s.charAt(i))) {
                        num = num * 10 + (s.charAt(i) - '0');
                        i++;
                    }
                    i--;
                    nums.push(num);
                }
                else if (s.charAt(i) == '(') {
                    ops.push(s.charAt(i));
                }
                else if (s.charAt(i) == ')') {
                    while (!ops.empty() && ops.peek() != '(') {
                        int b = nums.pop();
                        int a = nums.pop();
                        char op = ops.pop();
                        nums.push(calculate(a, b, op));
                    }
                    ops.pop(); // 弹出左括号
                }
                else { // 运算符
                    while (!ops.empty() && ops.peek() != '(' && 
                           priority(ops.peek()) >= priority(s.charAt(i))) {
                        int b = nums.pop();
                        int a = nums.pop();
                        char op = ops.pop();
                        nums.push(calculate(a, b, op));
                    }
                    ops.push(s.charAt(i));
                }
            }
            
            while (!ops.empty()) {
                int b = nums.pop();
                int a = nums.pop();
                char op = ops.pop();
                nums.push(calculate(a, b, op));
            }
            
            System.out.println(nums.peek());
        }
    }
}

def priority(op):
    if op in ['*', '/']: return 2
    if op in ['+', '-']: return 1
    return 0

def calculate(a, b, op):
    if op == '+': return a + b
    if op == '-': return a - b
    if op == '*': return a * b
    if op == '/': return a // b
    return 0

while True:
    try:
        s = input()
        nums = []  # 数字栈
        ops = []   # 运算符栈
        i = 0
        
        while i < len(s):
            if s[i] == ' ':
                i += 1
                continue
            
            # 处理负数
            if s[i] == '-' and (i == 0 or s[i-1] == '(' or s[i-1] in '+-*/'):
                nums.append(0)  # 在负数前添加0
            
            if s[i].isdigit():  # 数字
                num = 0
                while i < len(s) and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                nums.append(num)
                continue
                
            if s[i] == '(':  # 左括号
                ops.append(s[i])
            elif s[i] == ')':  # 右括号
                while ops and ops[-1] != '(':
                    b = nums.pop()
                    a = nums.pop()
                    op = ops.pop()
                    nums.append(calculate(a, b, op))
                ops.pop()  # 弹出左括号
            else:  # 运算符
                while ops and ops[-1] != '(' and priority(ops[-1]) >= priority(s[i]):
                    b = nums.pop()
                    a = nums.pop()
                    op = ops.pop()
                    nums.append(calculate(a, b, op))
                ops.append(s[i])
            i += 1
        
        while ops:
            b = nums.pop()
            a = nums.pop()
            op = ops.pop()
            nums.append(calculate(a, b, op))
        
        print(nums[0])
        
    except EOFError:
        break

算法及复杂度

算法：栈实现的表达式求值
时间复杂度： $\mathcal{O}(n)$ - 其中 $n$ 为表达式的长度
空间复杂度： $\mathcal{O}(n)$ - 需要两个栈来存储数字和运算符