逆波兰表达式:后缀表达式
波兰表达式:前缀表达式
计算后缀表达式:
当遇到一个数时就把它压入栈中,在遇到一个操作符时就将该操作符作用于该栈弹出的两个数上,并将结果压入栈中。
#include<stack> double evalPostFix( ) { stack<double> s; string token; double a, b, result; cin>> token; while (token[0] != '=') { result = atof (token.c_str()); if (result != 0.0 ) s.push(result); else if (token == "0.0") s.push(result); else switch (token[0]) { case '+' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push(b+a); break; case '-' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push(b-a); break; case '*' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push(a*b); break; case '/' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push(b/a); break; case '^' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push(exp(b*log(a))); break; } cin>> token; } return s.top(); }
中缀变后缀:
当读到一个操作数时,立即输出;当遇到操作符时,从栈中弹出并输出元素直到遇到优先级更低的操作符,该操作符进栈。对于“(”,将其压入栈中,除非是在处理“)”的时候,否则决不从栈中移走“(”,最后,如果读到输入的末尾,将栈元素弹出直到空栈。
int main() { stack<char> s; char token; cin>> token; while (token != '=') { if (token >= 'a' && token <= 'z') cout<<token<<" "; else switch (token) { case ')' : while(!s.empty() && s.top() != '(') { cout<<s.top()<<" "; s.pop();} s.pop(); break; case '(' : s.push(token); break; case '^' : while(!s.empty() && s.top()== '^') {cout<<s.top()<<" "; s.pop();} s.push(token); break; case '*' : case '/' : while(!s.empty() && s.top() != '+' && s.top() != '-' && s.top() != '(') {cout<<s.top()<<" "; s.pop();} s.push(token); break; case '+' : case '-' : while(!s.empty() && s.top() != '(' ) {cout<<s.top()<<" "; s.pop();} s.push(token); break; } cin>> token; } while (!s.empty()) {cout<<s.top()<<" "; s.pop();} cout<<"="<<endl; return 0; }
后缀变中缀:
跟计算后缀表达式差不多,只不过将操作数取出来的时候组成字符串压入栈中:
string postToInfix() { stack<string> s; string token; string a, b; cin>>token; while (token[0] != '=') { if (token[0] >= 'a' && token[0] <= 'z') s.push(token); else switch (token[0]) { case '+' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push("("+ a+" + " + b+")"); break; case'-' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push("("+a+" - "+ b+")"); break; case '*' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push("("+a+" * "+ b+")"); break; case '/' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push("("+a+" / " + b+")"); break; case '^' : a = s.top(); s.pop(); b = s.top(); s.pop(); s.push("("+a+" ^ " + b+")"); break; } cin>> token; } return s.top(); }
后缀变前缀:
原理同上。