25140: 根据后序表达式建立队列表达式

http://cs101.openjudge.cn/practice/25140/

后序算术表达式可以通过栈来计算其值，做法就是从左到右扫描表达式，碰到操作数就入栈，碰到运算符，就取出栈顶的2个操作数做运算(先出栈的是第二个操作数，后出栈的是第一个)，并将运算结果压入栈中。最后栈里只剩下一个元素，就是表达式的值。

有一种算术表达式不妨叫做“队列表达式”，它的求值过程和后序表达式很像，只是将栈换成了队列：从左到右扫描表达式，碰到操作数就入队列，碰到运算符，就取出队头2个操作数做运算（先出队的是第2个操作数，后出队的是第1个），并将运算结果加入队列。最后队列里只剩下一个元素，就是表达式的值。

给定一个后序表达式，请转换成等价的队列表达式。例如，3 4 + 6 5 * -的等价队列表达式就是5 6 4 3 * + - 。

输入

第一行是正整数n(n<100)。接下来是n行，每行一个由字母构成的字符串，长度不超过100,表示一个后序表达式，其中小写字母是操作数，大写字母是运算符。运算符都是需要2个操作数的。

输出

对每个后序表达式，输出其等价的队列表达式。

样例输入

2
xyPzwIM
abcABdefgCDEF

样例输出

wzyxIPM
gfCecbDdAaEBF

提示

建立起表达式树，按层次遍历表达式树的结果前后颠倒就得到队列表达式

来源：Guo Wei modified from Ulm Local 2007

The problem is asking to convert a postfix expression to an equivalent queue expression. The queue expression is obtained by reversing the level order traversal of the expression tree built from the postfix expression.

Here is a step-by-step plan:
1.Create a TreeNode class to represent each node in the tree. 2.Create a function build_tree that takes the postfix expression as input and returns the root of the constructed tree. Use a stack to store the nodes. Iterate over the characters in the postfix expression. If the character is an operand, create a new node and push it onto the stack. If the character is an operator, pop two nodes from the stack, make them the children of a new node, and push the new node onto the stack. 3.Create a function level_order_traversal that takes the root of the tree as input and returns the level order traversal of the tree. Use a queue traversal to store the nodes to be visited. While the queue is not empty, dequeue a node, visit it, and enqueue its children. 4.For each postfix expression, construct the tree, perform the level order traversal, reverse the result, and output it.

python

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_tree(postfix):
    stack = []
    for char in postfix:
        node = TreeNode(char)
        if char.isupper():
            node.right = stack.pop()
            node.left = stack.pop()
        stack.append(node)
    return stack[0]

def level_order_traversal(root):
    dq = [root]
    traversal = []
    while dq:
        node = dq.pop(0)
        traversal.append(node.value)
        if node.left:
            dq.append(node.left)
        if node.right:
            dq.append(node.right)
    return traversal

n = int(input().strip())
for _ in range(n):
    postfix = input().strip()
    root = build_tree(postfix)
    queue_expression = level_order_traversal(root)[::-1]
    print(''.join(queue_expression))

25140: 根据后序表达式建立队列表达式 ​

25140: 根据后序表达式建立队列表达式