题目链接:
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. 数组版
#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;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
Mastering Regular Expressions 3rd
regular expressions.
Introducing Regular Expressions pdf 高清 有目錄
Z.Expressions.Eval 4.0.68 包含.net3.1和 .net6的支持。不需要key,去除限制。
Walk away from old-fashioned and cumbersome query approaches and answer your business intelligence questions through simple and powerful queries built on common table expressions (CTEs) and window ...
书名:Mastering Regular Expressions, 3rd Edition 格式:CHM 语言:English 简介: Regular expressions are an extremely powerful tool for manipulating text and data. They are now standard ...
带有正则表达式的应用程序。 简约的UI 忘记按钮。只需键入您的模式并测试表达式。立即查看结果。 突出显示语法 不仅看起来不错,而且易于阅读。 参考表 总是忘记正则表达式的语法吗?只需按cmd r并查看参考表...
公式操作、表达式动态语句,可以考虑使用 Eval Expression。 本文件给你无限使用的特权,基于netstand2.1制作,可以方便的...需要下列包 ... <PackageReference Include="System.Xml.XPath" Version="4.3.0" />
JavaScript Regular Expressions 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传...
Mastering Regular Expressions, 2nd Edition
MariaDB and MySQL Common Table Expressions and Window Functions Revealed 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
You will begin by discovering what regular expressions are and how they work with Java. This easy-to-follow guide is a great place from which to familiarize yourself with the core concepts of regular ...
Teradata SQL Functions, Operators, Expressions, and Predicates
Mastering Regular Expressions.pdf
Regular expressions are used to describe patterns in text, and they are an invaluable aid when working with loosely formatted textual data. This little booklet describes Oracle's regular expression ...
[Regular.Expressions.Cookbook(2nd,2012,8)].Jan.Goyvaerts
Over the past decade, regular expressions have experienced a remarkable rise in pop- ularity. Today, all the popular programming languages include a powerful regular ex- pression library, or even have...
To introduce readers to regular expressions in several technologies. While the material is primarily for people who have little or no experience with regular expressions, there is also some content ...
Python_Regular_Expressions_-_Learn_Python_Regular_Expressions_in_an_Easy_Way.pdf