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

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

把带括号的一般正常的算式，转换成逆波兰式。

输入和输出如下例子：

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;
	}
}