面试经典150题 P224 基本计算器

---

时间轴

时间轴

2025-12-18

init

栈

---

题目：

P224 基本计算器

https://leetcode.cn/problems/basic-calculator/description/?envType=study-plan-v2&envId=top-interview-150

先转为前缀表达式，然后对前缀表达式求值

1. 需要先对字符去除空格，且对于负号(非减号，即单目运算符)在其前面插入 0 使得变为双目运算符。

   • '-'为第一个字符的是单目运算符即负号，前面插入 0

   • '-‘前面是’('的是单目运算符即负号，前面插入 0

   • 其他情况下’-'是双目运算符即减号

2. 然后转为前缀表达式，按空格分割各个操作数和操作符。首先创建一个存储符号的栈 opStack，记返回值为string ret，遍历中缀表达式的每个字符。

   • 对于数字，不断加入 ret 直到下一个是非数字，然后 ret 后加一个空格进行分割，表示这是一个操作数，方便后续对前缀表达式求值

   • 对于’('，直接加入 opStack

   • 对于’)‘，弹出 opStack 中的所有双目运算符(’+‘或’-‘或’*‘或’/‘)加入 ret，直到栈顶’(‘，弹出’('但不加入 ret

   • 对于双目运算符(‘+‘或’-‘或’*‘或’/’)

     • 如果栈顶元素也是双目运算符，且当前的双目运算符的优先级小于栈顶优先级，那么一直弹出栈顶直到不满足这个条件，最后把当前双目运算符加入栈中
     • 其他情况下，把当前双目运算符加入栈中。

   • 最后如果 opStack 不为空，则把剩下的元素依次弹出加入 ret

3. 最后对后缀表达式求值，注意求值最好用 long，最后转为 int

#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <sstream>

using std::stack;
using std::string;
using std::vector;

class Solution {
    public:
        int getPrecedence(char op)
        {
                if (op == '+' || op == '-')
                        return 1;
                if (op == '*' || op == '/')
                        return 2;
                return 0;
        }

        // 辅助：将字符串按空格分割
        vector<string> split(const string &s)
        {
                vector<string> tokens;
                std::istringstream iss(s);
                string token;
                while (iss >> token) {
                        tokens.push_back(token);
                }
                return tokens;
        }
        // 转为前缀表达式
        string conv_suffix_expr(string s)
        {
                string ret;
                stack<char> opStack;
                char ch;
                int i = 0, n = s.size();

                while (i < n) {
                        ch = s[i];

                        // 处理多位数字
                        if (std::isdigit(ch)) {
                                while (i < n && std::isdigit(s[i])) {
                                        ret += s[i];
                                        i++;
                                }
                                ret += " "; // 加空格分隔
                                i--; // 后面会i++
                        } else if (ch == '(') { // 左括号
                                opStack.push(ch);
                        } else if (ch == ')') { // 右括号
                                while (!opStack.empty() && opStack.top() != '(') {
                                        ret += opStack.top();
                                        ret += " ";
                                        opStack.pop();
                                }
                                if (!opStack.empty())
                                        opStack.pop(); // 弹出 '('
                        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') { // 运算符
                                while (!opStack.empty() &&
                                       getPrecedence(opStack.top()) > 0 && //栈顶也为双目运算符
                                       getPrecedence(opStack.top()) >= getPrecedence(ch)) { // 当前 ch 对应的运算符优先级小于栈顶的运算符优先级
                                        ret += opStack.top();
                                        ret += " ";
                                        opStack.pop();
                                }
                                opStack.push(ch);
                        }

                        i++; // 普通字符（运算符/括号）前进一位
                }

                // 弹出剩余运算符
                while (!opStack.empty()) {
                        ret += opStack.top();
                        ret += " ";
                        opStack.pop();
                }

                return ret;
        }
        // 前缀表达式求值
        int suffix_expr_cal(string &postfix)
        {
                vector<string> tokens = split(postfix);
                stack<long> st;
                long a, b;

                for (const string &token : tokens) {
                        if (token == "+" || token == "-" || token == "*" || token == "/") {
                                b = st.top();
                                st.pop();
                                a = st.top();
                                st.pop();
                                if (token == "+")
                                        st.push(a + b);
                                else if (token == "-")
                                        st.push(a - b);
                                else if (token == "*")
                                        st.push(a * b);
                                else if (token == "/")
                                        st.push(a / b);
                        } else {
                                st.push(std::stol(token));
                        }
                }

                return (int)st.top();
        }
        string handleUnaryMinus(const string &s)
        {
                string clean;
                for (char c : s) {
                        if (c != ' ')
                                clean += c;
                }

                string result;
                int n = clean.size();

                for (int i = 0; i < n; ++i) {
                        char c = clean[i];
                        if (c == '-') {
                                // 判断是否为一元负号：
                                // 情况1：开头
                                // 情况2：前一个字符是 '(' 或其他运算符 (+, -, *, /)
                                if (i == 0) {
                                        result += "0-";
                                } else {
                                        char prev = clean[i - 1];
                                        if (prev == '(') {
                                                result += "0-";
                                        } else {
                                                result += '-';
                                        }
                                }
                        } else {
                                result += c;
                        }
                }
                return result;
        }

        int calculate(string s)
        {
                s = handleUnaryMinus(s); // 在"-"前插入 0
                string postfix = conv_suffix_expr(s);
                return suffix_expr_cal(postfix);
        }
};

只有加减

由于字符串除了数字与括号外，只有加号和减号两种运算符。因此，如果展开表达式中所有的括号，则得到的新表达式中，数字本身不会发生变化，只是每个数字前面的符号会发生变化。括号不能忽略，因为虽然"+“和”-“运算优先级相同，但是括号会改变优先级。变化主要在于没有了双目运算符的优先级判断，即对于原来的"如果栈顶元素也是双目运算符，且当前的双目运算符的优先级小于栈顶优先级，那么一直弹出栈顶直到不满足这个条件，最后把当前双目运算符加入栈中”,变为"如果栈顶元素是双目运算符，那么一直弹出栈顶直到不满足这个条件，最后把当前双目运算符加入栈中"。

string conv_suffix_expr(string s) {
    string ret;
    stack<char> opStack;
    int i = 0, n = s.size();

    while (i < n) {
        char ch = s[i];

        if (std::isdigit(ch)) {
            while (i < n && std::isdigit(s[i])) {
                ret += s[i];
                i++;
            }
            ret += " ";
            i--;
        }eles if (ch == '(') {
            opStack.push(ch);
        }else if (ch == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                ret += opStack.top();
                ret += " ";
                opStack.pop();
            }
            if (!opStack.empty()) opStack.pop(); // pop '('
        }else if (ch == '+' || ch == '-') {
            // 弹出所有栈顶不是 '(' 的双目运算符
            while (!opStack.empty() &&
                   opStack.top() != '(' ) {
                ret += opStack.top();
                ret += " ";
                opStack.pop();
            }
            opStack.push(ch);
        }

        i++;
    }

    while (!opStack.empty()) {
        ret += opStack.top();
        ret += " ";
        opStack.pop();
    }

    return ret;
}