[算法学习]后缀表达式转二叉树

算法

问题描述： 输入后缀表达式，输出后缀表达式的二叉树。

解法与分析：

  1. 根据后缀表达式的特点，我们可以知道，只要是运算符的就都是根结点。
  2. 我们这里需要使用一个栈来保存字符。遍历后缀表达式，每当遇到是非运算符的字符，就将它入栈，当遇到是运算符，就将栈中前两个结点出栈，和运算符组成一棵子树，然后入栈。遍历完成后，栈中剩下的唯一的一个结点就是该后缀表达式的二叉树的根结点。

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 后缀表达式转二叉表达式树
 * @param suffixStr
 */
public static void suffixExpression2Tree(String suffixStr)
{
    if(isEmpty(suffixStr)) return;

    char[] chs=suffixStr.toCharArray();
    // 用于临时存储节点的栈
    Stack<TreeNode> stack=new Stack<TreeNode>();
    // 遍历所有字符，不是运算符的入栈，是运算符的，将栈中两个节点取出，合成一颗树然后入栈
    for(int i=0;i<chs.length;i++)
    {
        if(isOperator(chs[i]))
        {
            if(stack.isEmpty()||stack.size()<2)
            {
                System.err.println("输入的后缀表达式不正确");
                return;
            }
            TreeNode root=new TreeNode(chs[i]);
            root.left=stack.pop();
            root.right=stack.pop();
            stack.push(root);
        }
        else
        {
            stack.push(new TreeNode(chs[i]));
        }
    }
    if(stack.isEmpty()||stack.size()>1)
    {
        System.err.println("输入的后缀表达式不正确");
        return;
    }
    stack.pop().printAll();
}