11234 - Expressions | 1181 | 50.55% | 471 | 89.60% |
题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2175
题目类型: 数据结构, 二叉树
题目大意:
一般情况下,都是中缀操作符, 如x+y。然后题目给出了一种后缀操作符的形式, 变成 x y +。 进行后缀操作可以用栈模拟,使用push,pop, 过程和经典的“括号匹配”差不多。 然后要求我们转换成队列的方式,用队列的push和pop(队列的和栈的区别).
解体思路:
一开始没思路, 后来觉得听说是要建树。 这题也是我写的第一道二叉树题。
题目的最关键部分是进行二叉树建树, 以及层次遍历逆序输出,还有利用栈的“括号匹配”思想。 二叉树的基本结构是,父结点都是操作符,子节点都是数字。 对于给出的序列, 从左到右遍历,遇到代表数字的小写则建立一个无儿子的树,然后把根结点指针入栈, 遇到代表操作符的大写字母,则从栈中弹出两个根结点,然后建立一个以大写字母为根,弹出的两个操作数为左右儿子的树,再把这个新树的根结点指针压入栈。如此循环下去。 最后,在栈顶的那个指针就是最后建成的树的根结点。 然后对这颗树进行层次遍历把字母取出来,最后逆序输出即可。
样例输入:
2
xyPzwIM
abcABdefgCDEF
样例输出:
wzyxIPM
gfCecbDdAaEBF
代码:
1. 数组版
10278049 | 11234 | Expressions | Accepted | C++ | 1.512 | 2012-07-01 12:59:01 |
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
class Node{
public:
char data;
int left;
int right;
};
stack<int>st;
queue<int>qu;
Node arr[10005];
char str[10005];
int result[10005], resultIndex;
// 进行广搜层次遍历
void bfs(int root){
while(!qu.empty()) qu.pop();
qu.push(root);
result[resultIndex++]=arr[root].data;
while(!qu.empty()){
int t = qu.front();
qu.pop();
if(arr[t].left != -1){
result[resultIndex++] = arr[arr[t].left].data;
qu.push(arr[t].left);
}
if(arr[t].right != -1){
result[resultIndex++] = arr[arr[t].right].data;
qu.push(arr[t].right);
}
}
}
void Solve(){
while(!st.empty()) st.pop();
for(int i=0; i<strlen(str); ++i){
if(islower(str[i])){
st.push(i);
arr[i].data = str[i];
arr[i].left = -1;
arr[i].right = -1;
}
else{
int right = st.top();
st.pop();
int left = st.top();
st.pop();
arr[i].data = str[i];
arr[i].left = left;
arr[i].right = right;
st.push(i);
}
}
// 按层次遍历,把字母存在一个栈上(为了逆序输出),然后输出
resultIndex = 0;
bfs(st.top());
// 按广搜结果的逆序输出
for(int i=resultIndex-1; i>=0; --i)
printf("%c",result[i]);
printf("\n");
}
int main(){
freopen("input.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%s",str);
Solve();
}
return 0;
}
2. 指针动态内存分配版
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
class Node{
public:
char data;
Node* left;
Node* right;
};
stack<Node*>st;
queue<Node*>qu;
char str[10005];
int result[10005], resultIndex;
// 进行广搜层次遍历
void bfs(Node* root){
while(!qu.empty()) qu.pop();
qu.push(root);
result[resultIndex++]=root->data;
while(!qu.empty()){
Node* t = qu.front();
qu.pop();
if(t->left != NULL){
result[resultIndex++] = t->left->data;
qu.push(t->left);
}
if(t->right != NULL){
result[resultIndex++] = t->right->data;
qu.push(t->right);
}
}
}
void Solve(){
while(!st.empty()) st.pop();
for(int i=0; i<strlen(str); ++i){
if(islower(str[i])){
Node *temp = new Node;
temp->data = str[i];
temp->left = NULL;
temp->right = NULL;
st.push(temp);
}
else{
Node* right = st.top();
st.pop();
Node* left = st.top();
st.pop();
Node* parent = new Node;
parent->data = str[i];
parent->left = left;
parent->right = right;
st.push(parent);
}
}
// 按层次遍历,把字母存在一个栈上(为了逆序输出),然后输出
resultIndex = 0;
bfs(st.top());
// 按广搜结果的逆序输出
for(int i=resultIndex-1; i>=0; --i)
printf("%c",result[i]);
printf("\n");
}
int main(){
freopen("input.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%s",str);
Solve();
}
return 0;
}
—— 生命的意义,在于赋予它意义。
原创 http://blog.csdn.net/shuangde800 , By D_Double