Title link in here.

The requirement of this problem is to modify a suffix expression so that the push and pop operations of the queue can replace the push and pop of the stack.
After reading the question, I thought it was required to use queue instead of stack (you can baidu search "queue instead of stack"), but it seems to have nothing to do with this question hh
Here, grasp the essence of the problem and solve the problem in a simpler way.
Whether it is implemented by stack or queue, the first thing to be clear is what remains unchanged in the two ways.
It is recommended to understand the four traversal methods of binary trees before reading below
In fact, no matter what kind of data structure is used, the only thing that should not be changed is the operation order.
Therefore, you can first use the stack to obtain the operation binary tree corresponding to the suffix expression, which is uniquely determined.
Then consider how to use the push and pop operations of the stack to convert to this binary tree, and how to use the push and pop operations of the queue to obtain a string to obtain this binary tree.
Stack acquisition: read the expression circularly. If it is not an operator, set the left and right nodes to be empty and put on the stack; If it is an operator, two elements will be out of the stack, set as the left and right nodes of the operator, and put into the stack.
Queue acquisition: read the expression cyclically. If it is not an operator, set the left and right nodes to be empty and enter the queue; If it is an operator, two elements are sent out of the queue, which are respectively set as the left and right nodes of the operator and sent into the queue.
Because the first node in the queue must be the first to be out of the queue and participate in the formation of the parent node (if the queue is empty, it is to participate in the formation of the parent node without children, that is, the leaf node), the read expression must be from the bottom of the binary tree to the root node (in fact, it can be thought of as the reverse order of hierarchical traversal), In addition, in the actual operation, since the first to join the queue is calculated first, which is opposite to the stack, for two child nodes of the same node, the read expression must read the right child first and then the left child. To sum up, the expression to be read by the queue instead of the stack is actually the reverse order expression of the hierarchical traversal of the binary tree.
**So you can use the stack to generate this binary tree, then traverse the hierarchy, and finally output it in reverse order**

The detailed code is as follows:

Click to view the code

#include<iostream>
#include<stack>
#include<string>
#include<queue>
using namespace std;
/*
*Infix expression and suffix expression represent the results of traversal of binary tree in different ways
* You can use the stack to generate the binary tree according to the suffix expression
* Because the queue operation is equivalent to the hierarchical traversal of a binary tree
* Because the first queued node must be out of the queue first and participate in the formation of the parent node first (if the queue is empty, it is to participate in the formation of the parent node without children, that is, the leaf node), the read expression must be from the bottom of the binary tree to the root node, and the actual operation is opposite to the stack because the first queued node is calculated first, Therefore, for two child nodes of the same node, the read expression must read the right child first and then the left child. To sum up, the expression to be read by the queue instead of the stack is actually the reverse order expression of the hierarchical traversal of the binary tree.
* Therefore, you can use the queue to obtain the hierarchical traversal results of the binary tree, and then output them in reverse order
*/
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] != '\0'; 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;
	}
}