【洛谷 P1449】后缀表达式 题解（栈+分支）

后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

如：$\text{3*(5-2)+7}$ 对应的后缀表达式为：$\text{3.5.2.-*7.+@}$。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 $s$，表示后缀表达式。

输出格式

输出一个整数，表示表达式的值。

样例 #1

样例输入 #1

3.5.2.-*7.+@
1

样例输出 #1

16
1

提示

数据保证，$1\le |s|\le 50$，答案和计算过程中的每一个值的绝对值不超过 $10^9$。

---

思路

从输入中逐个读入字符，对于每个字符进行如下处理：

• 如果是 +、-、*、/ 中的一个，则从栈中弹出两个数 a 和 b，将其进行相应的运算后将结果 c 压入栈中。
• 如果是数字，则将其转化为整数 x，用一个变量存储。
• 如果是 .，说明当前数字已经读取完毕，将其压入栈中，并将 x 清零。
• 如果是 @，说明输入结束，跳出循环。

最后，输出栈顶元素即可得到结果。

---

AC代码

#include 
#include 
#define AUTHOR "HEX9CF"
using namespace std;

char ch;
stack<int> stk;

void getNum(int &a, int &b)
{
    b = stk.top();
    stk.pop();
    a = stk.top();
    stk.pop();
};

int main()
{
    int x = 0;
    while (~(ch = getchar()))
    {
        int a, b, c;
        if ('@' == ch)
        {
            break;
        }
        switch (ch)
        {
        case '+':
            getNum(a, b);
            c = a + b;
            stk.push(c);
            // cout << a << " + " << b << " = " << c << endl;
            break;
        case '-':
            getNum(a, b);
            c = a - b;
            stk.push(c);
            // cout << a << " - " << b << " = " << c << endl;
            break;
        case '*':
            getNum(a, b);
            c = a * b;
            stk.push(c);
            // cout << a << " * " << b << " = " << c << endl;
            break;
        case '/':
            int a, b, c;
            getNum(a, b);
            c = a / b;
            stk.push(c);
            // cout << a << " / " << b << " = " << c << endl;
            break;
        case '.':
            stk.push(x);
            x = 0;
            break;
        default:
            x = x * 10 + ch - '0';
        }
    }
    cout << stk.top() << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64