1356：计算(calc)

【题目描述】
小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)

【输入】
共1行，为一个算式。

【输出】
共1行，就是密码。

【输入样例】
1+(3+2)(7^2+69)/(2)
【输出样例】
258

分析

1. 解决思路：先将中缀表达式转化为后缀表达式，然后通过后缀表达式去求这个算式的值，关于后缀表达式求值，见：1331：【例1-2】后缀表达式的值；

2. 中缀表达式转化为后缀表达式：
   2.1.通过一个transform函数去实现这个功能，转换方法如下图：
   
   2.2 关于第五点也就是运算符进栈的条件：进栈的符号 优先级要大于 栈顶符号的优先级，否则一直出栈到可以放进去;特殊的如果栈顶为’(',则运算符可以直接放进去 (栈顶不是’('的，才进行优先级判断)；
   2.3 关于判断符号优先级的处理，我用了一个数组去标记每个运算符的优先级，来确定是否能进栈；
   2.4 需要注意 =!stk.empty() 这个条件，每次取栈中元素都要思考下需不需要加，防止出错；
   2.5 处理数字时，如果 直接拼str += s[i]; 后面没法区分原来的数是多少，比如最后得到了123+，你不知道是12+3还是1+23，所以我没直接把数字拼在str（存放后缀表达式的字符串）中，所以我用了个numStatus 去标记构造数字所处状态，在下一个字符不是数字时候，表示当前数字已构造完成，把它添加进str，然后额外往后面添加一个空格来区分数字；需要在遍历完字符串后，再进行一次判断，例如 1+3 numStatus=true状态时，没遇到符号去放入后缀式；（因为前面将数字放进str是通过遍历中下一次遇到的是运算符时候，结束构造状态，添加进str，如果数字后面没字符，就需要最后遍历结束额外去判断，如果构造状态numStatus=true，就把num放进str），如下图转化出来的后缀表达式；
   

   2.6 最后将栈内剩余运算符放入后缀表达式，不能忘；
   2.7 c++将数字拼接在字符串后面采用的是：to_string(num)

3. 参考：数据结构—栈的应用（中缀表达式转后缀表达式）、信息学奥赛一本通 1356：计算(calc)

#include 

using namespace std;

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

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

//中缀表达式转为后缀表达式
void transform() {
    //+ - * / ^进栈条件
    // 进栈的符号 优先级要大于 栈顶符号的优先级，否则一直出栈到可以放进去;
    // 特殊的如果栈顶为'(',则运算符可以直接放进去 (栈顶不是'('的，才进行优先级判断)
    bool numStatus = true;//在下一个字符不是数字时候，表示当前数字已构造完成
    int num = 0;
    for (int i = 0; i < s.size(); ++i) {
        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;
                case '^': stk_num.push(pow(b, a));break;
            }
        }
    }
}

int main() {
    cin >> s;
    //初始优先级数组
    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