点击打开链接
题目意思:给定一个字符串表示是一个表达式,要求使用队列代替栈的方法来输出结果。
解题思路:我们知道对于这个表达式,最后一个肯定是大写字母,对于每一个大写字母会跟着两个小写的字母或大写字母,那我们联想到二叉树,我们可以建立一颗二叉表达式的树,怎么建呢,一下代码详解,最后我们只要从最后一层从左往右这样输出即可,要求用到树的层次遍历(就是广搜),同时需要用一个list来存储节点的值,最后输出list即可
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 10010;
//树的结构
struct Btree{
char val;
Btree *lchild;
Btree *rchild;
Btree *father;
};
Btree *root ;
char expre[MAXN];//表达式数组
int t ;
list<char>l;//链表存储结果
queue<Btree*>q;//队列用来广搜
stack<Btree*>s;//栈用来建树
//节点初始化函数
void init(Btree *u , char c){
u->val = c;
u->lchild = NULL;
u->rchild = NULL;
}
//输出函数
//我们利用队列进行树的层次遍历,但是每次都先遍历右儿子,把右儿子的值存入list中,记住是往前插入,最后输出即可
void output(Btree *root){
q.push(root);
l.push_front(root->val);
while(!q.empty()){
root = q.front();
q.pop();
if(root->lchild != NULL || root->rchild != NULL){//只要不为空就要进行插入操作,先访问右节点
if(root->rchild != NULL){//如果右儿子不为空,把右儿子push进队列中 ,并且则把右儿子的值插入list中
q.push(root->rchild);
l.push_front(root->rchild->val);
}
if(root->lchild != NULL){//如果左儿子不为空,把左儿子push进队列中 ,并且则把左儿子的值插入list中
q.push(root->lchild);
l.push_front(root->lchild->val);
}
}
}
list<char>::iterator it;//一个list迭代器来输出
for(it = l.begin() ; it != l.end() ; it++)
cout<<*it;
cout<<endl;
}
//建树函数、
//从左往右,我们知道大写字母一定是某一颗子树的根节点,那么我们从左到右,是小写字母就建立一个点并把值赋给它,然后把节点压入栈中,当遇到大写字母时,建立根节点,把栈中的两个节点分别赋为该根节点的儿子,并且出栈,同时把次根节点如栈,更新root,直到最后一个
void solve(){
Btree *temp;
root = new Btree;//分配空间,记住没有分配空间是不能赋值的
char ch;
for(int i= 0 ; i != strlen(expre) ; i++){
if(islower(expre[i])){//小写字母
temp = new Btree;//建立一个临时的Btree*
init(temp , expre[i]);//赋值函数
s.push(temp);//压入栈
}
else{
temp = new Btree;
init(temp , expre[i]);//建立根节点
temp->lchild = s.top();//左儿子为栈顶
s.pop();//清除栈顶
temp->rchild = s.top();//右儿子为栈顶
s.pop();//清除栈顶
if(i != strlen(expre)-1)//如果不是最后一个就把根节点入栈
s.push(temp);
root = temp;//更新root
}
}
output(root);
while(!q.empty())//注意队列的情空
q.pop();
l.clear();//注意对list的清空
}
//主函数
int main(){
cin>>t;
getchar();
while(t--){
gets(expre);
solve();
}
return 0;
}
分享到:
相关推荐
regular-expressions-cheat-sheet-v2.pdf,正则表达式备忘单
davechild_regular-expressions davechild_regular-expressions davechild_regular-expressions davechild_regular-expressions davechild_regular-expressions
var expressions = require ( "angular-expressions" ) ; evaluate = expressions . compile ( "1 + 1" ) ; evaluate ( ) ; // returns 2 您还可以在给定scope设置和获取值: evaluate = expressions . compile ...
python-regular-expressions-cheat-sheet
( 13-Java-8-Lambda-Expressions-Part-1.pdf ) java 8 lambda- expressions 学习资料,例子。练习 java example
本文使用时间差值模型LBP—TOP方法为特征提取方法,分类器采用支持向量机,随机森林,多核学习作为分类器,同时采用了一种微表情诱发方法
前端开源库-reshape-expressions重塑表达式、局部变量、表达式、循环和条件
Regular-Expressions.info
babel-plugin-transplace-expressions 用其他表达式替换JavaScript表达式。安装$ yarn add --dev babel-plugin-transform-replace-expressions例输入文件: const env = process . env . NODE_ENV ;typeof Hello ===...
资源来自pypi官网。 资源全名:node-expressions-0.1.1.tar.gz
rubygem-cucumber-tag_expressionsrubygem-cucumber-tag_expressions
编译时正则表达式v3 快速的编译时正则表达式,支持在编译时或运行时进行匹配/搜索/捕获。 您可以使用目录single-header的单头版本。 可以使用make single-header重新生成此make single-header 。...
此存储库已移至DOM Expressions Mono存储库。 此存储库不再被维护。 去这里: : Babel插件JSX DOM表达式 该软件包是为构建的JSX编译器,可为React式库提供一般的JSX到DOM转换,以进行精细的变化检测。 该软件包旨在...
DOM表达式 DOM表达式是React库的渲染运行时,可进行细粒度的更改检测。 这些库依赖于诸如Observables和Signals之类的概念,而不是依赖生命周期功能和虚拟DOM。 标准JSX转换器对这些库没有帮助,因为它们需要单独评估...
Regular Google Analytics
基本正则表达式的学习,python入门,适合新手使用
Mastering-Python-Regular-Expressions 精通Python正则表达式
ECMAScript throw表达式 该提议定义了新的语法以从表达式上下文中引发异常。 地位 阶段: 2 冠军:罗恩·巴克顿(@rbuckton) 有关更多信息,请参阅。 作者 罗恩·巴克顿(@rbuckton) 提议 throw表达式使您可以在...
ECMAScript建议: do表达式 该提案有。 地位 该提案处于第一阶段。 动机 面向表达式的编程是FP的一大进步 表达式像乐高积木一样塞在一起,从而在较小的范围内提供了更具延展性的编程体验 例子 以面向表达式的风格...
算术和逻辑表达式使用面向协议的二叉树优雅地建模和可视化.