首页 > 代码库 > UVA11234 Expressions

UVA11234 Expressions

题目的意思实在是读不懂,又是把栈变成队列什么的。。不过大体的意思就是把后缀表达式变一下。。

抛开意思,其实就是根据输入建个树,然后倒序输出。。

拿第一个样例说明;大写代表操作符(+ - × /之类的)小写代表数字。。

xyPzwIM:就是指 (xPy) M (zIw) 就像是两数相乘1 × 2写成 12×;

变成树的样子就是

     M

    / |

   P   I

  / |  / |

 x  y z  w


然后把这棵数倒着输出 wzyxIPM;

建树时就是碰到小写,就建个小树,左子树右子数都是空,压入栈;

碰到大写,也要建个小树,并把栈顶两个元素取出来,作为做子树和右子树。。在把新树压入栈

建完后栈顶就是这个树的根,采用广搜遍历就行。。


AC代码:


#include<iostream>
#include<string>
#include<stack>
#include<stdlib.h>
#include<queue>
using namespace std;

const int N = 100010;
struct node{
	char value;
	node *left,*right;
};
int main () {
	int T;
	stack<node*> sta;
	queue<node*> que;
	cin >> T;
	while (T--) {
		string str;
		cin >> str;
		for (int i = 0 ; i < str.size() ;i++) {
			if (str[i] >='a' && str[i] <='z') {
				node* u =(node*)malloc(sizeof(node));
				u -> value = http://www.mamicode.com/str[i];>



UVA11234 Expressions