codechef Transform the Expression 转换成逆波兰式

版权声明：本文作者靖心，靖空间地址：http://blog.csdn.net/kenden23/。未经本作者同意不得转载。 https://blog.csdn.net/kenden23/article/details/24902179

把一般式子转换成逆波兰式。

这里的都是加括号的，难度减少点。

Example

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 遇到括号')'，就出栈一个操作符 - 注意不是全部操作符出栈

不带括号的操作差别就在于是否须要推断符号的优先级。

#include <stack>
#include <stdio.h>
#include <iostream>
using namespace std;

int TransformTheExpression()
{
	int T = 0, c = 0, id = 0;
	scanf("%d
", &T);
	char buffer[40200];
	char res[40200];
	stack<char> stk;
	if ((c = fread(buffer, 1, 40200, stdin)) > 0)
	{
		for (int i = 0; i < c; i++)
		{
			if ('(' == buffer[i]) continue;

			if ( buffer[i] == '+' || buffer[i] == '-' ||
				buffer[i] == '*' || buffer[i] == '/' || buffer[i] == '^')
			{
				stk.push(buffer[i]);
			}
			else if (buffer[i] == ')')
			{
				res[id++] = stk.top();
				stk.pop();
			}
			else	res[id++] = buffer[i];
		}
	}
	fwrite(res, sizeof(char), id, stdout);
	return 0;
}