UVa 11234 - Expressions

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2175

#include <iostream>

#include <string>

#include <stack>

#include <queue>

#include <cctype>

#include <algorithm>

using namespace std;

struct Node

{

char c;

int num, left, right;

Node():left(-1), right(-1) {}

};

int main()

{

int T;

string s;

cin >> T;

while(T--)

{

cin >> s;

Node tree[10005];

stack<Node> st;

for(int i = 0; i < s.size(); ++i) //建树

{

if(islower(s[i]))

{

tree[i].c = s[i];

tree[i].num = i;

st.push(tree[i]);

}

else

{

Node a, b, d;

a = st.top();

st.pop();

b = st.top();

st.pop();

tree[i].c = s[i];

tree[i].num = i;

tree[i].left = b.num;

tree[i].right = a.num;

st.push(tree[i]);

}

string ans;

queue<Node> q;

q.push(tree[s.size() - 1]);

while(!q.empty()) //层次遍历

{

Node tmp = q.front();

ans += tmp.c;

q.pop();

Node x;

if(tmp.left != -1)

{

x = tree[tmp.left];

q.push(x);

}

if(tmp.right != -1)

{

x = tree[tmp.right];

q.push(x);

}

reverse(ans.begin(), ans.end());

cout << ans << endl;

}

return 0;

}

posted on 2011-11-23 16:16 wuxu 阅读(216) 评论(0) 编辑收藏引用所属分类: 数据结构

常用链接

留言簿(1)

随笔分类

随笔档案

收藏夹

友情链接

搜索

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。


相关文章: UVa11235 - Frequent values UVa 10562 - Undraw the Trees UVa 699 - The Falling Leaves UVa 297 - Quadtrees UVa 548 - Tree UVa 112 - Tree Summing UVa 540 - Team Queue UVa 11234 - Expressions hdu1166【线段树】 hdu3415【单调队列】

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理