BV1LY4y1v7AC

Untitled

class Solution {
public:
    void eval() {
        auto b = nums.top(); nums.pop();
        auto a = nums.top(); nums.pop();
        char c = op.top(); op.pop();

        if (c == '+') nums.push(a + b);
        if (c == '-') nums.push(a - b);
        printf("%d %c %d\\n", a, c, b);
    }

    int calculate(string _s) {
        string s;
        // 去除空格
        for (char ch : _s)
            if (ch != ' ')
                s += ch;
        cout << "Input s: " << s << endl;

        for (int i = 0; i < s.size(); i ++) {
            char c = s[i];
            if (isdigit(c)) { // 是数字
                long long x = 0; int j = i;
                while (j < s.size() && isdigit(s[j])) {
                    x = x * 10 + s[j++] - '0';
                }
                i = j - 1;
                cout << "isdigit: push <- " << x << endl;
                nums.push(x);
            } else if (c == '(') {
                op.push(c);
            } else if (c == ')') { // 右括号，计算到左括号为止
                while (op.top() != '(') eval();
                op.pop();
            } else { // 运算符
                if (i == 0 || s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-') { // 处理特殊情况
                    nums.push(0);
                }
                while (!op.empty() && op.top() != '(') eval();
                op.push(c);
            }
        }
        while (!op.empty()) eval();
        return nums.top();
    }

private:
    stack<char> op;
    stack<long long> nums;
};

表达式求值

+ - * / 括号

https://www.acwing.com/problem/content/3305/

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

stack<int> num;
stack<char> op;

//优先级表
unordered_map<char, int> h{ {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };

void eval()//求值
{
    int a = num.top();//第二个操作数
    num.pop();

    int b = num.top();//第一个操作数
    num.pop();

    char p = op.top();//运算符
    op.pop();

    int r = 0;//结果 

    //计算结果
    if (p == '+') r = b + a;
    if (p == '-') r = b - a;
    if (p == '*') r = b * a;
    if (p == '/') r = b / a;

    num.push(r);//结果入栈
}

int main()
{
    string s;//读入表达式
    cin >> s;

    for (int i = 0; i < s.size(); i++)
    {
        if (isdigit(s[i]))//数字入栈
        {
            int x = 0, j = i;//计算数字
            while (j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + s[j] - '0';
                j++;
            }
            num.push(x);//数字入栈
            i = j - 1;
        }
        //左括号无优先级，直接入栈
        else if (s[i] == '(')//左括号入栈
        {
            op.push(s[i]);
        }
        //括号特殊，遇到左括号直接入栈，遇到右括号计算括号里面的
        else if (s[i] == ')')//右括号
        {
            while(op.top() != '(')//一直计算到左括号
                eval();
            op.pop();//左括号出栈
        }
        else
        {
            while (op.size() && h[op.top()] >= h[s[i]])//待入栈运算符优先级低，则先计算
                eval();
            op.push(s[i]);//操作符入栈
        }
    }
    while (op.size()) eval();//剩余的进行计算
    cout << num.top() << endl;//输出结果
    return 0;
}

作者：Hasity
链接：<https://www.acwing.com/solution/content/40978/>
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个题目看起来简单是因为

题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,