POJ 3367 Expressions 表达式运算

题目链接在这里

本题的要求是把一个后缀表达式作一定的修改,使之用队列的push和pop操作可以代替栈的push和pop。
读完题本来以为题目要求,用队列来代替栈(可以百度搜索“队列代替栈”),然而好像跟本题没什么关系hh
这里抓住问题的本质,用更简单的方式解决问题。
不管是使用堆栈来实现,还是使用队列来实现,首先要明确的是两种方式处理表达式不变的是什么。
《建议在阅读下面之前理解一下二叉树的四种遍历方式》
两种方式处理表达式不变的是实际的运算顺序,事实上不论用什么样的数据结构,唯一不应该改变的就是运算顺序。
所以可以先用堆栈来获取这个后缀表达式对应的运算二叉树,这个二叉树是唯一确定的。
然后分别考虑如何用堆栈的push和pop操作转化为这颗二叉树,以及如何用队列的push和pop操作一个字符串获取这颗二叉树。
堆栈获取:循环读取表达式,如果不是运算符就设置左右节点为空,入栈;如果是运算符就出栈2个元素,分别设置为该运算符的左右节点,入栈。
队列获取:循环读取表达式,如果不是运算符就设置左右节点为空,入队列;如果是运算符就出队列2个元素,分别设置为该运算符的左右节点,入队列。
因为最先入队的节点一定最先出列,最先参与构成父节点(如果这时队列为空的话,是参与构成没有孩子的父节点,也就是叶子节点),所以读取的表达式一定是从二叉树的最底层到根节点,(到这里其实就可以想到是层次遍历的逆序了),而且实际运算的时候由于先入队的先计算,与栈相反,所以对于同一个节点的两个孩子节点,读取的表达式一定是先读右孩子再读左孩子。综上所述,这里队列代替栈要读取的表达式实际上是二叉树的层次遍历的逆序表达式。
** 所以可以先用堆栈生成这课二叉树,然后层次遍历,最后逆序输出即可。**

详细的代码如下:

点击查看代码
#include<iostream> #include<stack> #include<string> #include<queue> using namespace std; /* *中缀表达式、后缀表达式分别代表二叉树不同方式遍历的结果 * 可以根据后缀表达式利用栈来生成这课二叉树 * 因为队列操作相当于是一颗二叉树的层次遍历 * 因为最先入队的节点一定最先出列,最先参与构成父节点(如果这时队列为空的话,是参与构成没有孩子的父节点,也就是叶子节点),所以读取的表达式一定是从二叉树的最底层到根节点,而且实际运算的时候由于先入队的先计算,与栈相反,所以对于同一个节点的两个孩子节点,读取的表达式一定是先读右孩子再读左孩子。综上所述,这里队列代替栈要读取的表达式实际上是二叉树的层次遍历的逆序表达式。 * 所以可以利用队列获得二叉树的层次遍历结果,再逆序输出即可 */ struct Node { 	Node* left, * right; 	char e; }; Node nodes[10005]; char expressions[10005]; int main() { 	int testNum, i; 	stack<Node*> stk; 	queue<Node*> queue; 	cin >> testNum; 	string str; 	int length; 	Node* temp; 	while (testNum--) { 		memset(expressions, 0, sizeof(expressions)); 		cin >> expressions; 		length = strlen(expressions); 		for (int i = 0; expressions[i] != ''; i++) { 			if (expressions[i] <= 'z' && expressions[i] >= 'a') 			{ 				nodes[i].left = NULL; 				nodes[i].right = NULL; 				nodes[i].e = expressions[i]; 				stk.push(&nodes[i]); 			} 			else 			{ 				nodes[i].right = stk.top(); 				stk.pop(); 				nodes[i].left = stk.top(); 				stk.pop(); 				nodes[i].e = expressions[i]; 				stk.push(&nodes[i]); 			} 		} 		queue.push(stk.top()); 		i = 0; 		while (queue.size() > 0) { 			temp = queue.front(); 			queue.pop(); 			expressions[i] = temp->e; 			if (temp->left != NULL) { 				queue.push(temp->left); 				queue.push(temp->right); 			} 			i++; 		} 		for (i = length - 1; i >= 0; i--) { 			cout << expressions[i]; 		} 		cout << endl; 	} }  

推荐这些文章:

jpa条件表达式Expressions.booleanTemplate

if (queryRO.getSpecialQuery().equals("1")) { builder.and(Expressions.booleanTemplate("{0} - 15 > {1}", qAbroadRegistrationInfo.endDate, qAbroadRegistrationInfo.beginDate));} else if (queryRO.getSpecialQuery().equals("2")) { builder.and(Expressions.booleanTemplate("{0} - 15 > {1}", qAbro...

【算法】二叉树的各种遍历方式

1.前序遍历
根-左-右的顺序遍历,可以使用递归
void preOrder(Node *u){
if(u==NULL)return;
printf("%d ",u->val);
preOrder(u->l);preOrder(u->r);
}

2.中序遍历
左-根-右的顺序遍历,可以使用递归
void inOrder(Node *u){
if(u==NULL)return;
inOrder(u->l);
printf("%d ",u->val);
inOrder(u->r);
}

3.后序遍历
...

94.二叉树专题(前中后序遍历)

目录递归法迭代法迭代法的统一写法
(https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/che-di-chi-tou-er-cha-shu-de-qian-zhong-y0emt/)
递归法

前序遍历

class Solution {
public:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
re...

二叉树的四种遍历

1.前序遍历;
先访问根结点,然后再访问左子树,最后访问右子树
2.中序遍历
先访问左子树,中间访问根节点,最后访问右子树
3.后序遍历;
先访问左子树,再访问右子树,最后访问根节点
1、前序遍历
/*
* 路人假helloWorld
*/
//前序遍历
//获取整个树中所有的键
public Queue<Key> preErgodic(){
Queue<Key> keys = new Queue<>();
preErgodic(root,keys);
return keys;
}
//获取指定树x的所有键,并放入到keys队列中
...

队列(queue)的方法

size();
insert(i,d) : 在index i 插入d;
delete(i) : 删除index为i 的元素, index省略就删除整个q
pop_front(), pop_back();
push_front(d), push_back(d).
 

...

二叉树 非递归 遍历

先序遍历
先序遍历的顺序是 根 左孩子 右孩子
递归写法
public void dfs(Node node){
if(node == null) {
return;
}
System.out.println(node.val);
dfs(node.left);
dfs(node.right);
}
}

递归的写法还是挺简单的,下面让我们看一下非递归的写法
非递归的写法
非递归与递归的不同点在于非递归需要一个栈来记录节点
先根遍历 是先打印根 那么我们就直接把根节点进行打印,然后...

【每日一题】【队列的实现类】【每层元素个数】2022年1月11日-NC15 求二叉树的层序遍历

描述给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)例如:给定的二叉树是{3,9,20,#,#,15,7},

 
 
 
注意:每一层上元素的个数
解答:

import java.util.*;

/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/

public class Solution {
ArrayList<ArrayList<Inte...

【数据结构】二叉树的前/中/后序遍历

前序遍历
递归实现
//递归实现前序遍历
public static void PreOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.println(head);
PreOrderRecur(head.left);
PreOrderRecur(head.right);
}

非递归实现
//非递归实现前序遍历
public static void PreOrderUnRecur(Node head) {
if (head == null) {
...

文章标题:POJ 3367 Expressions 表达式运算
文章链接:https://www.dianjilingqu.com/2797.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>