逆波兰表达式c++

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
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
stack<char> table;   //无括号符号存储栈
stack<char> table2;  //有括号符合存储栈
int Priority(char x)
{
    switch(x)
    {
        case '*':
            return 2;
        case '/':
            return 2;
        case '+':
            return 1;
        case '-':
            return 1;
        case '#':
            return 0;
    }
}
string Mid_to_Back(string str) //无括号中缀表达式转换为后缀表达式
{
    string s;   //记录结果
    
    for (int i = 0; i < str.size();i++)
    {
        if(str[i] >= '0' && str[i] <= '9')  //如果是数字则记录
            s += str[i];    
        else if (str[i] == '*' || str[i] == '/' || str[i] == '+' || str[i] == '-')  
        {
            if(Priority(str[i]) > Priority(table.top()))     //大于栈顶符号优先级，则将符号入栈。
            {
                table.push(str[i]);
                continue;
            }
            while(Priority(str[i]) <= Priority(table.top()))    //如果不大于
            {
                s += table.top();                               //则记录栈顶符号
                table.pop();                                    //然后出栈
            }
            table.push(str[i]);                       
        }                           //以9+2*3+5为例
    }
    while(table.top() != '#')       //以9+2*3为例。循环出栈
    {
        s += table.top();
        table.pop();
    }
    return s;
}
string Mid_to_Back_with_Kh(string str)  //有括号中缀表达式转换为后缀表达式
{
    string s;   //记录结果
    for (int i = 0; i < str.size();i++)
    {
        if(str[i] >= '0' && str[i] <= '9')  //如果是数字则记录
        {
            s += str[i];
        }
        else if(str[i] == '(')  //如果是左括号则入栈（不考虑括号的优先级）
        {
            table2.push(str[i]);
        }
        else if(str[i] == ')')  //如果是右括号则遍历栈中符号先记录后出栈
        {
            while(table2.top() != '(')
            {
                s += table2.top();
                table2.pop();
            }
            table2.pop();       //将左括号出栈
        }
        else if (str[i] == '*' || str[i] == '/' || str[i] == '+' || str[i] == '-')
        {
            if(table2.top() == '(') //栈顶符号是（，则入栈
            {
                table2.push(str[i]);
            }
            else    //不是则比较优先级
            {
                if(Priority(str[i]) > Priority(table2.top()))   //大于则入栈
                {
                    table2.push(str[i]);
                    continue;
                }
                while(Priority(str[i]) <= Priority(table2.top()) && table2.top() != '(') 
                {						 //小于且栈顶符号不为左括号，防止与左括号做优先级比较
                    s += table2.top();
                    table2.pop();
                }
                table2.push(str[i]);    //直到栈顶符号优先级小于字符中符号的优先级或栈顶为左括号，将符号入栈。
            }       //以9*（3-1*5）*2/3+4与9*（3*5-1）*2/3+4为例
        }
    }
    while(table2.top() != '#')
    {
        s += table2.top();
        table2.pop();
    }
    return s;
}
void test04()
{
    table.push('#');    //为将字符串中第一个符号入栈，对栈内初始符号定义为优先级最小的字符。
    table2.push('#');
    string str;
    while(cin >> str)
    {
        string str_temp = Mid_to_Back_with_Kh(str);
        cout << "后缀表达式为：" << str_temp << endl;
        stack<int> s_temp;  
        for (int i = 0; i < str_temp.size();i++)    //计算后缀表达式
        {
            if(str_temp[i] >= '0' && str_temp[i] <= '9')    //数字则入栈
            {
                s_temp.push(str_temp[i] - '0');
            }
           else if (str_temp[i] == '*' || str_temp[i] == '/' || str_temp[i] == '+' || str_temp[i] == '-')
           {
               int t1 = s_temp.top();       //字符则将栈中的前两个值与符号进行运算
               s_temp.pop();
               int t2 = s_temp.top();
               s_temp.pop();
               if(str_temp[i] == '*')
               {
                   s_temp.push(t2 * t1);
               }
               if(str_temp[i] == '/')
               {
                   s_temp.push(t2 / t1);
               }
               if(str_temp[i] == '+')
               {
                   s_temp.push(t2 + t1);
               }
               if(str_temp[i] == '-')
               {
                   s_temp.push(t2 - t1);
               }
           }
        }
        int ans = s_temp.top(); //最后的数字即为运算结果
        cout << ans << endl;
    }
}
int main()
{
    test04();
    return 0;
}