1358：中缀表达式值(expr)

【题目描述】
输入一个中缀表达式（由0-9组成的运算数、加+减-乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。

注意：必须用栈操作，不能直接输出表达式的值。

【输入】
一行为一个以@结束的字符串。

【输出】
如果表达式不合法，请输出“NO”，要求大写。

如果表达式合法，请输出计算结果。

【输入样例】
1+2*8-9@
【输出样例】
8

分析

1. 基于这个：1356：计算(calc)，多加了一个判断合法性条件，别的几乎一模一样，这里说下判断表达式是否合法；
2. 此题的合法性，从这两个方面判断即可通过测试点，①判断括号是否匹配，可以参考：1353：表达式括号匹配(stack)；②判断是否出现连续的运算符，比如++、+*这些；
3. 通过一个judge函数去判断表达式是否合法，通过isCalc函数判断一个字符是否是+ - * /运算符；
4. 当然判断表达式是否合法，还有别的考虑条件，比如除数不为0，)(两个括号之间需要运算符了，这些测试点也没，我也没去判断；可以参考：信息学奥赛一本通 1358：中缀表达式值(expr)、1358：中缀表达式值(expr)(一本通)

#include 

using namespace std;

string s;
stack<char> stk;//符号栈
stack<int> stk_num;//数字栈，为了求值用
string str;//保存后缀表达式
int pri[100];//设定每个符号的优先级（ascii码为i的运算符）

//判断一个字符是否是运算符
bool isCalc(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

//判断表达式是否合法
bool judge() {
    //1.判断括号匹配
    stack<char> st;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '@')
            break;
        if (s[i] == '(')
            st.push(s[i]);
        else if (s[i] == ')') {
            if (st.empty()) {
                return false;
            }
            st.pop();
        }
    }
    if (!st.empty())
        return false;
    //2.判断是否连续出现运算符
    for (int i = 0; i < s.length() - 1; ++i) {
        //不能出现类似于：++、+*、++**
        if (isCalc(s[i]) && isCalc(s[i + 1])) {
            return false;
        }
    }
    return true;
}

//初始化符号优先级数组
void init() {
    pri[')'] = 1;//优先级最低，也就是可以实现遇到左括号之前全部出栈
    pri['+'] = 2;
    pri['-'] = 2;
    pri['*'] = 3;
    pri['/'] = 3;
    pri['('] = 4;//优先级最高，可以实现左括号直接进栈
}

//中缀表达式转为后缀表达式
void transform() {
    //+ - * / ^进栈条件
    // 进栈的符号 优先级要大于 栈顶符号的优先级，否则一直出栈到可以放进去;
    // 特殊的如果栈顶为'(',则运算符可以直接放进去 (栈顶不是'('的，才进行优先级判断)
    bool numStatus = true;//在下一个字符不是数字时候，表示当前数字已构造完成
    int num = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '@')
            break;
        if (s[i] >= '0' && s[i] <= '9') {
            //str += s[i];  直接拼 后面没法区分原来的数是多少
            numStatus = true;
            num = num * 10 + (s[i] - '0');
        } else if (s[i] == '(') {
            //如果在构造数字状态，将其结束，放入后缀式
            if (numStatus) {
                str += (to_string(num) + " ");
                num = 0;
                numStatus = false;
            }
            stk.push(s[i]);
        } else if (s[i] == ')') {
            if (numStatus) {
                str += (to_string(num) + " ");
                num = 0;
                numStatus = false;
            }
            //遇到右括号，将遇到左括号之前的所有符号出栈
            while (stk.top() != '(') {
                str += stk.top();
                stk.pop();
            }
            //此时栈顶为'('，然后将其出栈，但不放进后缀表达式
            stk.pop();
        } else {
            if (numStatus) {
                str += (to_string(num) + " ");
                num = 0;
                numStatus = false;
            }
            //此时为+ - * / ^这些运算符
            //栈不空才去判断优先级，否则直接入栈
            //只要栈内 存在比 当前 优先级高的、同级的，一直出栈;
            //但栈顶为'(',则运算符可以直接放进去
            while (!stk.empty() && pri[s[i]] <= pri[stk.top()] && stk.top() != '(') {
                str += stk.top();
                stk.pop();
            }
            stk.push(s[i]);
        }
    }
    //需要注意：例如 1+3 numStatus=true状态时，没遇到符号去放入后缀式
    if (numStatus) {
        str += (to_string(num) + " ");
    }
    //将栈内剩余运算符放入后缀表达式
    while (!stk.empty()) {
        str += stk.top();
        stk.pop();
    }
}

//根据后缀表达式str求值
void cal() {

    for (int i = 0; i < str.size(); ++i) {
        int num = 0;
        if (str[i] >= '0' && str[i] <= '9') {
            //构造这个数,空格为构造当前数字完成的标志
            while (str[i] != ' ') {
                num = num * 10 + (str[i] - '0');
                i++;
            }
            stk_num.push(num);
        } else {
            //运算
            int a = stk_num.top();
            stk_num.pop();
            int b = stk_num.top();
            stk_num.pop();
            switch (str[i]) {
                case '+':
                    stk_num.push(b + a);
                    break;
                case '-':
                    stk_num.push(b - a);
                    break;
                case '*':
                    stk_num.push(b * a);
                    break;
                case '/':
                    stk_num.push(b / a);
                    break;
            }
        }
    }
}


int main() {
    cin >> s;
    //判断表达式合法性
    if (!judge()) {
        cout << "NO";
        return 0;
    }
    //初始优先级数组
    init();
    //将中缀转化为后缀字符串str
    transform();
    //计算后缀表达式str的值
    cal();
    cout << stk_num.top();
    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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171