最近在刷算法题时，遇到了实现计算器的问题。一开始觉得很简单，但真正动手实现时才发现其中有很多细节需要考虑。今天就来分享一下我的实现思路和学到的经验。

问题分析

我们需要实现一个能够处理加减乘除四则运算的计算器，要正确处理运算符的优先级（乘除优先于加减），同时还要处理空格和多位数字。

解决方案：中缀表达式转后缀表达式

我选择的方法是中缀表达式转后缀表达式（逆波兰表达式），然后再计算后缀表达式。这种方法虽然需要两个步骤，但逻辑清晰，易于理解和实现。

第一步：中缀转后缀

cpp

int calculate(string s) {vector<string> postfix;  // 存储后缀表达式stack<string> opStack;   // 运算符栈for (int i = 0; i < s.size();) {// 跳过空格if (s[i] == ' ') {i++;continue;}// 处理数字if (isdigit(s[i])) {string num;while (i < s.size() && isdigit(s[i])) {num += s[i++];}postfix.push_back(num);} // 处理运算符else {string op(1, s[i++]);// 处理运算符优先级if (op == "+" || op == "-") {// 加减优先级最低，弹出所有运算符while (!opStack.empty()) {postfix.push_back(opStack.top());opStack.pop();}opStack.push(op);} else if (op == "*" || op == "/") {// 乘除优先级较高，只弹出同优先级的运算符while (!opStack.empty() && (opStack.top() == "*" || opStack.top() == "/")) {postfix.push_back(opStack.top());opStack.pop();}opStack.push(op);}}}// 弹出栈中剩余的所有运算符while (!opStack.empty()) {postfix.push_back(opStack.top());opStack.pop();}return evalRPN(postfix);
}

第二步：计算后缀表达式

cpp

int evalRPN(vector<string>& tokens) {stack<int> st;for (auto& e : tokens) {if (isdigit(e[0]) || (e.size() > 1 && e[0] == '-')) {st.push(stoi(e));} else {int n1 = st.top(); st.pop();int n2 = st.top(); st.pop();switch (e[0]) {case '+': st.push(n2 + n1); break;case '-': st.push(n2 - n1); break;case '*': st.push(n2 * n1); break;case '/': if (n1 == 0) throw runtime_error("Division by zero");st.push(n2 / n1); break;}}}return st.top();
}