PTA（栈和队列）2-5 逆波兰表达式求值

2-5 逆波兰表达式求值

分数 6

作者 李廷元

单位 中国民用航空飞行学院

逆波兰表示法是一种将运算符（operator）写在操作数（operand）后面的描述程序（算式）的方法。举个例子，我们平常用中缀表示法描述的算式（1 + 2）*（5 + 4），改为逆波兰表示法之后则是1 2 + 5 4 + *。相较于中缀表示法，逆波兰表示法的优势在于不需要括号。

请输出以逆波兰表示法输入的算式的计算结果。

输入格式:

在一行中输入1个算式。相邻的符号（操作数或运算符）用1个空格隔开。

输出格式:

在一行中输出计算结果。

限制:

2≤算式中操作数的总数≤100

1≤算式中运算符的总数≤99

运算符仅包括“+”、“-”、“*”，操作数、计算过程中的值以及最终的计算结果均在int范围内。

输入样例1:

1
4 3 + 2 -

输出样例1:

1
5

输入样例2:

1
1 2 + 3 4 - *

输出样例2:

1
-3

我的问题代码1

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
#include <iostream>
#include <stack>

using namespace std;

// 比较操作符，用于比较优先级
int compareOper(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*') return 2; // 题目说仅包括+-*
    else return 0;
}

// 计算表达式
int calculate(int num1, char top, int num2) {
    switch (top) {
        case('+'):
            return num1 + num2;
        case('-'):
            return num1 - num2;
        case('*'):
            return num1 * num2;
    }
}

int main() {
    stack<int> opnd; // 存放操作数的栈
    stack<char> oper; // 存放操作符的栈
    string str;
    cin >> str; // 读取后缀表达式
    for (int i = 0; i < str.length(); i++) {
        char c = str[i];
        if (isdigit(c)) { // 如果读取到的是数字
            opnd.push(c); // 进操作数栈
        } else if (c == ' ') { // 如果读取到的是空格
            continue; // 进行下一次循环
        } else { // 读取到的是操作符
            if (oper.empty()) { // 如果当前栈空
                oper.push(c); // 直接入栈
            } else { // 栈非空，就要开始比较操作符大小了
                // 如果输入的优先级大于栈顶的，直接入栈
                if (compareOper(c) > compareOper(oper.top())) {
                    oper.push(c);
                } else { // 否则栈中同等级的先做运算，直到栈顶的优先级比输入的小
                    while (compareOper(c) <= compareOper(oper.top())) {
                        char top = oper.top(); // 获取运算符
                        oper.pop();
                        int num2 = opnd.top(); // 获取右操作数
                        opnd.pop();
                        int num1 = opnd.top(); // 获取左操作数
                        opnd.pop();
                        // 开始做运算
                        int result = calculate(num1, top, num2);
                        opnd.push(result); // 结果入操作数栈
                    }
                }
            }
        }
    }
    cout << opnd.top();
}

逆波兰表达式计算逻辑错误

逆波兰表达式（后缀表达式）的计算规则是 遇到运算符直接取栈顶两个操作数计算，无需比较运算符优先级（优先级已通过后缀顺序体现），但你的代码保留了中缀表达式的优先级比较逻辑，完全多余且错误：

  • 比如输入样例 1 4 3 + 2 -，遇到 + 时无需判断优先级，直接取 4 和 3 计算；遇到 - 时直接取 7 和 2 计算。
  • 你的代码中 oper 栈和 compareOper 函数都是中缀转后缀的逻辑，逆波兰求值根本不需要。

其他细节错误

  1. 输入读取方式错误用cin >> str读取输入时，遇到空格会停止，无法读取完整的表达式（如输入4 3 +只会读取到4），导致后续解析失败。
  2. 操作数压入栈的是字符转成ASCII码的结果，应该压入栈的是字符-‘0’

我的问题代码2

测试点 提示 内存(KB) 用时(ms) 结果 得分
0 344 2 答案正确 3 / 3
1 520 2 答案正确 1 / 1
2 492 2 答案错误 0 / 2 
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
#include <iostream>
#include <stack>

using namespace std;

//// 比较操作符，用于比较优先级
//int compareOper(char c) {
//    if (c == '+' || c == '-') return 1;
//    if (c == '*') return 2; // 题目说仅包括+-*
//    else return 0;
//}

// 计算表达式
int calculate(int num1, char top, int num2) {
    switch (top) {
        case('+'):
            return num1 + num2;
        case('-'):
            return num1 - num2;
        case('*'):
            return num1 * num2;
    }
}

int main() {
    stack<int> opnd; // 存放操作数的栈
//    stack<char> oper; // 存放操作符的栈
    string str;
    getline(cin, str); // 读取后缀表达式
    for (int i = 0; i < str.length(); i++) {
        char c = str[i];
        if (isdigit(c)) { // 如果读取到的是数字
            opnd.push(c - '0'); // 进操作数栈
        } else if (c == ' ') { // 如果读取到的是空格
            continue; // 进行下一次循环
        } else { // 读取到的是操作符
            int num2 = opnd.top(); // 获取右操作数
            opnd.pop();
            int num1 = opnd.top(); // 获取左操作数
            opnd.pop();
            // 开始做运算
            int result = calculate(num1, c, num2);
            opnd.push(result); // 结果入操作数栈
        }
    }
    cout << opnd.top();
}

致命问题：无法处理多位数

当输入的操作数是多位数（如 12、100 等）时，代码会将其拆成单个字符处理。例如输入 12 3 +：

  • 循环遍历字符串时，'1' 会被解析为数字 1 入栈，'2' 会被解析为数字 2 入栈。
  • 实际需要的操作数是 12，但代码会错误地当成 1 和 2 两个数字，最终计算 1 + 2 + 3（错误），而非 12 + 3（正确）。

正确代码

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
#include <iostream>
#include <stack>

using namespace std;

//// 比较操作符，用于比较优先级
//int compareOper(char c) {
//    if (c == '+' || c == '-') return 1;
//    if (c == '*') return 2; // 题目说仅包括+-*
//    else return 0;
//}

// 计算表达式
int calculate(int num1, char top, int num2) {
    switch (top) {
        case('+'):
            return num1 + num2;
        case('-'):
            return num1 - num2;
        case('*'):
            return num1 * num2;
    }
}

int main() {
    stack<int> opnd; // 存放操作数的栈
//    stack<char> oper; // 存放操作符的栈
    string str;
    getline(cin, str); // 读取后缀表达式
    for (int i = 0; i < str.length(); i++) {
        char c = str[i];
        if (isdigit(c)) { // 如果读取到的是数字
            int num = 0;
            while (i < str.length() && isdigit(str[i])) {
                num = num * 10 + (str[i] - '0');
                i++;
            }
            opnd.push(num); // 进操作数栈
        } else if (c == ' ') { // 如果读取到的是空格
            continue; // 进行下一次循环
        } else { // 读取到的是操作符
            int num2 = opnd.top(); // 获取右操作数
            opnd.pop();
            int num1 = opnd.top(); // 获取左操作数
            opnd.pop();
            // 开始做运算
            int result = calculate(num1, c, num2);
            opnd.push(result); // 结果入操作数栈
        }
    }
    cout << opnd.top();
}