ReZero's Utopia.

求后缀表达式

Word count: 613Reading time: 3 min
2016/11/02 Share

规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

//中缀表达式转后缀表达式的方法:
//1.遇到操作数:直接输出(添加到后缀表达式中)
//2.栈为空时,遇到运算符,直接入栈
//3.遇到左括号:将其入栈
//4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。
//5.遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
//6.最终将栈中的元素依次出栈,输出。
//fork from http://www.cnblogs.com/mygmh/archive/2012/10/06/2713362.html
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
#include <iostream>
#include <map>
#include <stack>
#include <cstdio>
using namespace std;

map<char, int> sym;
void init(){
sym.insert(make_pair('+',1));
sym.insert(make_pair('-',1));
sym.insert(make_pair('*',2));
sym.insert(make_pair('/',2));
}

bool isInt(char c){
return (c >= '0' && c <= '9');
}

double calc(double a, double b, char c){
if(c == '+') return a+b;
else if(c == '-') return b-a;
else if(c == '*') return b*a;
return b/a;

}

int main(){
string ss;
init();
int kase = 1;
while(cin >> ss){
cout << "Case #" << kase++ << ":" << endl;
stack<char> last;
stack<double> answer;
int qsize = ss.size();

for(int i = 0; i < qsize; ++i){
if(isInt(ss[i])){ /// num is the true num
double num = 0;
while(isInt(ss[i])){
num = num * 10 + ss[i] - '0';
++i;
}
int point = 0;
if(ss[i] == '.') {
++i;

while(isInt(ss[i])){
num = num * 10 + ss[i] - '0';
++i; ++point;
}
--i;
for(int j = 0; j < point; ++j){
num /= 10.0;
}

} else --i;
printf("%.*lf ", point, num);
answer.push(num);

}
else if (last.empty() || ss[i] == '('){
last.push(ss[i]);
}
else if(ss[i] == ')') {
while(last.top() != '('){
///calculate the num
double a = answer.top(); answer.pop();
double b = answer.top(); answer.pop();
answer.push(calc(a,b, last.top()));


///epichar
cout << last.top();
last.pop();
}
last.pop();
}
else{
while(!last.empty() && sym[ss[i]] <= sym[last.top()]){
double a = answer.top(); answer.pop();
double b = answer.top(); answer.pop();
answer.push(calc(a,b, last.top()));

cout << last.top();
last.pop();
}
last.push(ss[i]);
}
}
while(!last.empty()) {
double a = answer.top(); answer.pop();
double b = answer.top(); answer.pop();
answer.push(calc(a,b, last.top()));

cout << last.top();
last.pop();
}
cout << endl;
cout << "The answer is ";
double ans = answer.top();
printf("%g",ans);
cout << "." <<endl << endl;
}
}

/**************************************************************
Language: C++
Result: Accepted
Time:1668 ms
Memory:1296 kb
****************************************************************/
CATALOG