洛谷P1981 表达式求值 题解 栈/中缀转后缀

题目链接：https://www.luogu.org/problem/P1981

这道题目就是一道简化的中缀转后缀，因为这里比较简单，只有加号（+）和乘号（*），所以我们只需要开一个存放数值的栈就可以了（如果涉及加减乘除则需要开另一个用于存放符号的栈）。

首先，我们读取一个整数并将其入栈。

然后接下来我们就是一个符号+一个数字这样的读取了。

每次我们读取一个符号和一个数字num：

• 如果符号是 + ，则判断一下当前栈中有多少元素，如果有超过1个元素，则将栈中所有元素出栈，并将它们的和入栈；
• 如果符号是 * ，则取出栈顶元素，并且取出来的栈顶元素与num的乘积在入栈。

当输入结束是，栈中的所有元素的乘积就是我们的答案。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int MOD = 10000;

int num;

char c;

stack<int> stk;

int main() {

    scanf("%d", &num);

    num %= MOD;

    stk.push(num);

    while ( (c = getchar()) != EOF ) {

        if (c != '*' && c != '+') break;

        scanf("%d", &num);

        num %= MOD;

        if (c == '+') {

            while (stk.size() > 1) {

                int a = stk.top(); stk.pop();

                int b = stk.top(); stk.pop();

                stk.push( (a + b) % MOD );

            }

            stk.push(num);

        }

        else if (c == '*') {

            int a = stk.top(); stk.pop();

            stk.push(a * num % MOD);

        }

    }

    while (stk.size() > 1) {

        int a = stk.top(); stk.pop();

        int b = stk.top(); stk.pop();

        stk.push( (a + b) % MOD );

    }

    printf("%d\n", stk.top());

    return 0;

}