SPOJ Transform the Expression 逆波兰式算法题解

SPOJ Transform the Expression 逆波兰式算法题解2015-02-25把带括号的一般正常的算式，转换成逆波兰式。

输入和输出如下例子：

Input:
3
（a+（b*c））
（（a+b）*（z+x））
（（a+t）*（（b+（a+c））^（c+d）））

Output:
abc*+
ab+zx+*
at+bac++cd+^*

总结规律是很困难的事情，总结好就能很快解决：

1 字母直接放结果

2 ‘（’入栈

3 ‘）’ 出栈到‘（’，然后出栈‘（’

4 操作符比较，高优先级的全部出栈，入结果，操作符入栈

#include <iostream>#include <string>#include <queue>#include <stack>using namespace std;int opToint（char op）{if （"+" == op） return 0;if （"-" == op） return 1;if （"*" == op） return 2;if （"/" == op） return 3;if （"^" == op） return 4;return -1;}bool cmpOP（char a, char b）{return opToint（a） - opToint（b） < 0;}string handleRPN（string &express）{string ans;stack<char> stk;for （int i = 0; i < express.size（）; i++）{if （"a" <= express[i] && express[i] <= "z"） ans.push_back（express[i]）;else if （"（" == express[i]） stk.push（express[i]）;else if （"）" == express[i]）{while （！stk.empty（） && "（" ！= stk.top（））{ans.push_back（stk.top（））;stk.pop（）;}if （！stk.empty（） && "（" == stk.top（）） stk.pop（）;}else{while （！stk.empty（） && "（" ！= stk.top（） && ！cmpOP（stk.top（）, express[i]） ）{ans.push_back（stk.top（））;stk.pop（）;}stk.push（express[i]）;}}return ans;}void TransformTheExpressionToRPN（）{string express;int T = 0;cin>>T;while （T--）{cin>>express;cout<<handleRPN（express）<<endl;}}

From：csdn博客靖心