0%

栈的应用——表达式求值

Posted on Edited on In Valine:

利用栈对表达式进行求解

描述

输入一个表达式（用字符串表示），求这个表达式的值。

保证字符串中的有效字符包括【0-9】、+、-、 *、/ 、(、 )、[、]、{ 、}，且表达式一定合法。

  • 输入描述：

    输入一个算术表达式

  • 输出描述：

    得到计算结果

示例一

输入：
$3+2{1+2[-4/(8-6)+7]}$
输出：
25

示例二

输入：
$5-3+96(6-10-2)$
输出：
-322

中缀表达式的计算

将中缀转后缀、后缀表达式的计算两个步骤合并。

  • 初始化两个栈，操作数栈和运算符栈

  • 从左到右扫描中缀表达式，

    • 当扫描到操作数时，将操作数压入操作数栈

    • 当扫描到运算符时，

      • 如果是界限符，

        • 遇到左括号’(‘、’[‘、’{‘，压入运算符栈

        • 遇到右括号’)’、’]’、’}’，依次弹出栈内的运算符，直到弹出左括号时结束

      • 如果是其他运算符，

        • 依次弹出优先级大于等于当前运算符的所有运算符，直到遇到左括号或栈空

        • 当前运算符入栈

  • 扫描完全部字符后，依次将剩下的运算符全部弹出

  • 每弹出一个运算符，就要弹出两个操作数，先弹出的为右操作数，后弹出的为左操作数，计算$[左操作数 \ 运算符\ 右操作数]$，将结果压入操作数栈

代码实现

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//弹出一个运算符和两个操作数，计算后的结果压入操作数栈
void pop_count_push (stack<int>& v_num, stack<char>& v_sign) {
    //运算符出栈
    char sign = v_sign.top();
    v_sign.pop();

    //操作数出栈，先弹出的为右操作数，后弹出的为左操作数
    int num1 = v_num.top(); //右操作数
    v_num.pop();
    int num2 = v_num.top(); //左操作数
    v_num.pop();

    //计算【左操作数 运算符 右操作数】
    int res;
    switch (sign) {
        case '+':
            res = num2 + num1;
            break;

        case '-':
            res = num2 - num1;
            break;

        case '*':
            res = num2 * num1;
            break;

        case '/':
            res = num2 / num1;
            break;

        default:
            break;
    }

    //结果压入操作数栈
    v_num.push(res);
}

//判断运算符优先级，乘除为2，加减为1
int priority (char c) {
    if (c == '*' || c == '/') {
        return 2;
    } else {
        return 1;
    }
}

//计算中缀表达式
int count_expression (string str) {
    stack<int> v_num; //操作数栈
    stack<char> v_sign; //运算符栈

    //如果开始或左括号后直接跟“-”号，则补0（即-4变0-4）
    for (int i = 0; i < str.length(); ++i) {
        if (i == 0 && str[i] == '-') {
            str = "0" + str;
        } else if (str[i] == '-' && (str[i - 1] == '(' || str[i - 1] == '[' ||
                                     str[i - 1] == '{')) {
            str.insert(i, "0");
        }
    }

    //从左到右扫描中缀表达式
    bool flag =
        false; //前一位为符号位为false，为数位为true（用于计算多位数）
    for (char c : str) {
        //当扫描到操作数时，将操作数压入操作数栈
        if (c >= '0' && c <= '9') {
            //前一位为符号位，则直接压入本位
            if (!flag) {
                flag = true;
                v_num.push(c - '0');
            }
            //前一位为数位，则将上一个数出栈，乘10，再加上本位
            else {
                int num = v_num.top() * 10 + (c - '0');
                v_num.pop();
                v_num.push(num); //新数入栈
            }
        }

        //当扫描到运算符时
        else {
            flag = false;

            //当扫描到左括号时，压入运算符栈
            if (c == '(' || c == '[' || c == '{') {
                v_sign.push(c);
            }

            //当扫描到右括号时，依次弹出栈内的运算符，直到弹出左括号时结束
            else if (c == ')' || c == ']' || c == '}') {
                //当栈顶不是左括号时，继续弹出运算符计算
                while (v_sign.top() != '(' && v_sign.top() != '[' && v_sign.top() != '{') {
                    pop_count_push(v_num, v_sign);
                }
                //弹出左括号
                v_sign.pop();
            }

            //当扫描到其他运算符时
            else {
                //遇到左括号或栈空前，一直弹出优先级大于等于当前的运算符
                while (!v_sign.empty()) {
                    if (v_sign.top() == '(' || v_sign.top() == '[' || v_sign.top() == '{') {
                        break;
                    }
                    //栈顶运算符的优先级大于等于当前的运算符，则弹出运算符计算
                    if (priority(v_sign.top()) >= priority(c)) {
                        pop_count_push(v_num, v_sign);
                    } else {
                        break; //否则结束弹出
                    }
                }
                //当前运算符入栈
                v_sign.push(c);
            }
        }
    }

    //将剩下的运算符全部弹出
    while (!v_sign.empty()) {
        pop_count_push(v_num, v_sign);
    }

    int result = v_num.top();
    return result;
}

int main () {
    string str;
    cin >> str;

    cout << count_expression(str) << endl;
}