acwing-3302. 表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 2³¹?1。
• 题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1?4)=?1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 10⁵。

输入样例：

(2+2)*(1+1)

输出样例：

8

方法一：

DNA动了这题

做法：

通过两个栈操作数栈nums，操作符栈ops，将中缀表达式转后缀表达式来做，下面复习一遍流程

1. 遇到操作数直接入栈nums
2. 遇到操作符，根据优先级( * / + - )的递减，若ops栈顶的操作符优先级比读入的高或相等，弹出ops栈顶操作符进行运算，直到栈空或栈顶不符合弹出要求，然后将读入的操作符入栈，注意优先级最低的)不用入栈
3. 全部读完后，若将ops中剩下的操作符自顶向下拿出来运算

其中上述的运算规则为：将nums栈顶的两个操作数拿出来与将要运算的操作符进行运算（见calc函数）

补充：

cin.peek()取输入流第一个字符而不消耗字符，旨在决定下一步是读入数字还是字符

#include 

using namespace std;

stack nums;
stack ops;

void calc(char o) {
    int n1 = nums.top();
    nums.pop();
    int n2 = nums.top();
    nums.pop();
    if (o == '+') nums.push(n2+n1);
    else if (o == '-') nums.push(n2-n1);
    else if (o == '*') nums.push(n2*n1);
    else if (o == '/') nums.push(n2/n1);
}

void op(char o) {
    if (ops.empty()) {
        ops.push(o);
        return;
    }
    char top = ops.top();
    if (o == '*' || o == '/') {
        while (top == '*' || top == '/') {
            ops.pop();
            calc(top);
            if (ops.empty()) break;
            top = ops.top();
        }
    } else if (o == '+' || o == '-') {
        while (top != '(') {
            ops.pop();
            calc(top);
            if (ops.empty()) break;
            top = ops.top();
        }
    } else if (o == ')') {
        while (top != '(') {
            ops.pop();
            calc(top);
            top = ops.top();
        }
        ops.pop(); // pop '('
    }

    if (o != ')') ops.push(o);
}

int main() {
    char c;
    int num;
    while (cin.peek() != '\n' && cin.peek() != EOF) {
        if (isdigit(cin.peek())) {
            cin >> num;
            nums.push(num);
        } else {
            cin >> c;
            op(c);
        }
    }

    while (!ops.empty()) {
        calc(ops.top());
        ops.pop();
    }
    cout << nums.top();
}