NYOJ--郁闷的C小加（一）

郁闷的C小加（一）

时间限制：1000 ms  |  内存限制：65535 KB 难度：3

描述

我们熟悉的表达式如a+b、a+b*(c+d)等都属于中缀表达式。中缀表达式就是（对于双目运算符来说）操作符在两个操作数中间：num1 operand num2。同理，后缀表达式就是操作符在两个操作数之后：num1 num2 operand。ACM队的“C小加”正在郁闷怎样把一个中缀表达式转换为后缀表达式，现在请你设计一个程序，帮助C小加把中缀表达式转换成后缀表达式。为简化问题，操作数均为个位数，操作符只有+-*/ 和小括号。

输入

第一行输入T，表示有T组测试数据（T<10）。

每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个表达式。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。并且输入数据不会出现不匹配现象。

输出

每组输出都单独成行，输出转换的后缀表达式。

样例输入

2      

1+2      

(1+2)*3+4*5      

样例输出

12+      

12+3*45*+      

解析：直接切入正题，很明显是将中缀表达式转换为后缀表达式，后缀表达式也成为逆波兰式，我们常见的表达式就是中缀表达式，后缀表达式就是将操作数放到前面，运算符放到后面，思想是中缀表达式-->建立二叉树-->后序遍历就是得到后缀表达式。第一次开始做感觉建二叉树太麻烦，于是想直接一次遍历字符串，将运算符压入符号栈中是否可以，当然可以，将运算符压入栈中，如果遇到当前的运算符的优先级低的话就先出栈，反之入栈。这个地方稍微有一点点复杂，弄清楚就好了。运算符栈如果开始压入#的话，可以在某些出栈的情况下要判断栈是否为空，原理都是以一样的，关键是思想哈！

代码如下：

#include <iostream>
#include <string>
#include <stack>
using std::endl;
using std::cin;
using std::cout;
using std::string;
using std::stack;
//定义运算符的优先级
int priority(char ch)
{
	int num;
	switch(ch)
	{
	case '+':
	case '-':
		num=1;
		break;
	case '*':
	case '/':
		num=2;
		break;
	case '(':
	case ')':
		num=0;
		break;
	default:
		num=-1;
		break;
	}
	return num;
}
int main()
{
	int T;
	cin >> T;
	//定义保存运算符的栈
	stack<char> op;
	op.push('#');
	while(T--)
	{
		string str1,str2;
		cin >> str1;
		//将中缀表达式转换为后缀表达式
		for(int i=0;i<str1.length();++i)
		{//扫描一遍输入的字符串进行转换
			if(str1[i]=='(')
			{
				op.push(str1[i]);
			}else if(str1[i]==')')
			{
				//遇到(则停止弹出
				while(op.top()!='(')
				{
					str2+=op.top();
					op.pop();
				}
				//将左括号从栈中弹出
				op.pop();
			}else if(str1[i]=='+'||str1[i]=='-'||str1[i]=='*'||str1[i]=='/')
			{
				//如果当前的操作符比栈顶的操作符优先级大的话，则将当前操作符压入栈
				if(priority(str1[i])>priority(op.top()))
				{
					op.push(str1[i]);
				}else{
					//当前运算符优先级小，则将栈中运算符优先级大于等于当前的都从栈中弹出来
					while(priority(op.top())>=priority(str1[i]))
					{
						str2+=op.top();
						//将栈顶的运算符弹出
						op.pop();
					}
					//然后再压入当前的运算符
					op.push(str1[i]);
				}
			}else{
				//当是数字的时候
				str2+=str1[i];
			}
		}
		//如果此时符号栈仍不为空则全部出栈
		while(op.top()!='#')
		{
			str2+=op.top();
			op.pop();
		}
		cout << str2 << endl;
	}
	return 0;
}
           

AC了之后，想想还是锻炼一下二叉树，因为自己最近在练一些数据结构(好久之前的东西，现在才捡起来，感觉自己好水哈)，所以想试试用中缀表达式来重建二叉树，原理就是这个二叉树的所有叶子节点都是操作数，而内节点都是运算符，定义了数据结构，写了创建节点的函数，剩下的就是跟上面一样了分析遇到的每个情况作出不同的选择，开始自己在写完代码，一直出现RE，我猜可能是指针有问题了，结果发现自己在一个地方分配节点后对叶子节点的左右孩子没有赋为NULL，唉……细心哈！

贴个代码，相互学习下哈！

#include <iostream>
#include <string>
#include <stack>
#include <malloc.h>
using std::endl;
using std::cin;
using std::cout;
using std::string;
using std::stack;
//定义树的节点
typedef struct node{
	char value;
	struct node *lchild;
	struct node *rchild;
}BiNode,*BTree;
//定义运算符的优先级
int priority(char ch)
{
	int num;
	switch(ch)
	{
	case '+':
	case '-':
		num=1;
		break;
	case '*':
	case '/':
		num=2;
		break;
	case '(':
	case ')':
		num=0;
		break;
	default:
		num=-1;
		break;
	}
	return num;
}
//定义运算符栈和操作数栈
stack<char> op;
stack<BiNode*> num;
//由运算符栈的栈顶和操作数栈的栈顶前两个元素组成一个树节点
void CreateNode(BTree &T)
{
	T=(BTree)malloc(sizeof(BiNode));
	T->value=op.top();
	op.pop();
	T->rchild = num.top();
	num.pop();
	T->lchild = num.top();
	num.pop();
	//然后压入操作数栈
	num.push(T);
}
//由中缀表达式建立二叉树
//s为中缀表达式
void CreateBTree(const string &s,BTree &T)
{
	for(int i=0;i<s.length();++i)
	{
		if(s[i]=='(')
		{
			op.push(s[i]);
		}else if(s[i]==')')
		{
			while(op.top()!='(')
			{
				CreateNode(T);
			}
			//将左括号弹出运算符栈
			op.pop();
		}else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')
		{//当前指向的是运算符时
			//运算符栈中的运算符优先级大于等于当前运算符的优先级的话，则先计算前面的
			while(!op.empty()&&priority(op.top())>=priority(s[i]))
			{
				//组成二叉树的节点
				CreateNode(T);
			}
			//然后将当前运算符压入运算符栈中去
			op.push(s[i]);
		}else{
			//当为数字的时候，组成节点压入操作数栈
			T=(BTree)malloc(sizeof(BiNode));
			T->value = s[i];
			T->rchild = NULL;
			T->lchild = NULL;
			num.push(T);
		}
	}
	//当字符栈非空的时候
	while(!op.empty())
	{
		//组成二叉树的节点
		CreateNode(T);
	}
}
//后序遍历建立的二叉树
void PostOrder(BTree &T)
{
	if(T!=NULL)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		cout << T->value;
	}
}
int main()
{
	int N;
	cin >> N;
	while(N--)
	{
		BTree T=NULL;
		string s;
		cin >> s;
		//执行过该函数后T就是由中缀表达式建立的二叉树
		CreateBTree(s,T);
		PostOrder(T);
		cout << endl;
	}
	return 0;
}