实现计算器从表达式求值

双栈解法

思路

• 一个栈nums存放数值，一个栈ops存放符合（运算符和括号）；
• 遍历字符串有四种情况：
  • 左括号：直接入ops栈；
  • 右括号：从现有的两个栈里面计算，直到遇到左括号；
  • 数字：取出整数放入nums栈；
  • 运算符：先把两个栈里面可以计算的都计算，然后将新运算符加入ops栈；
• 注意事项：
  • 处理字符串前先将空格去除；
  • 每次计算得到的结果同样存放在nums栈中；
  • 只有「栈内运算符」比「当前运算符」优先级高/同等，才进行栈里面的运算；
  • 由于第一个数可能是负数，可以先在nums栈中加入一个0占位；
  • 左括号后面也可能有负数，遇到时也往nums栈中加入一个0占位；

代码

#include <iostream>
#include <stack>
#include <memory>
#include <string>

using namespace std;

class Caculater {
private:
    string s;  // 待计算字符串

    int ans;  // 计算结果

    stack<int>  nums;  // 存数值
    stack<char> ops;   // 存操作符和括号

    // 返回操作符优先级
    int priority(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    }

    // 去除空格
    void removeSpace() {
        string tmp;
        for (char ch : s) {
            if (ch != ' ') tmp += ch;
        }
        s = tmp;
    }

    // 从 nums 中取出两个操作数，从 ops 中取出运算符，然后计算
    void compute() {
        if (nums.size() < 2 || ops.empty()) return;
        // x op y
        int y = nums.top(); nums.pop();
        int x = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        
        int ret = 0;
        if (op == '+') ret = x + y;
        else if (op == '-') ret = x - y;
        else if (op == '*') ret = x * y;
        else if (op == '/') ret = x / y;
        
        nums.push(ret);
    }

    void process() {
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.push(0);

        int n = s.size();
        for (int i = 0; i < n; ++i) {
            char ch = s[i];
            if (ch == '(') {
                // 遇到左括号就入栈
                ops.push(ch);
            } else if (ch == ')') {
                // 遇到右括号就计算，直到栈里面的左括号
                while (!ops.empty() && ops.top() != '(') compute();
                //if (ops.top() == '(') 
                ops.pop();  // 弹出'(',其实不用判断，因为有右括号必定有左括号
            } else if (isdigit(ch)) {
                // 遇到数字，就取出入数值栈
                int j      = i;
                int number = 0;
                while (j < n && isdigit(s[j])) {
                    number = 10 * number + (s[j] - '0');
                    ++j;
                }
                nums.push(number);
                i = j - 1; // 不能是i = j，因为for循环里面有++i；
            } else {
                // 遇到运算符
                // 为防止括号内出现的首个字符为运算符
                if (i > 0 && s[i - 1] == '(') {
                    nums.push(0);
                }
                // 有一个新操作要入栈时，先把栈内可以算的都算了
                // 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
                while (!ops.empty() && ops.top() != '(') {
                    char op = ops.top();
                    if (priority(op) >= priority(ch)) {
                        compute();
                    } else {
                        break;
                    }
                }
                ops.push(ch);
            }
        }
        // 计算剩余的
        while (!ops.empty() && ops.top() != '(') compute();
        
        ans = nums.top();
        while (!nums.empty()) nums.pop();  // 清理计算结果
    }

public:
    bool input() {
        cout << "please typeing correct caculate str here...\n";
        if (getline(cin, s)) return true;
        return false;
    }

    void output() { cout << "caculate result is: " << ans << endl; }

    void run() {
        while (input()) {
            removeSpace();
            process();
            output();
        }
    }
};

int main() {
    auto ptr = make_unique<Caculater>();
    ptr->run();
    return 0;
}

【参考文章】宫水三叶的刷题日记