首页 > 代码库 > codechef Transform the Expression 转换成逆波兰式

codechef Transform the Expression 转换成逆波兰式

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

这里的都是加括号的,难度降低点。

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\n", &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;
}