【数据结构与算法】总结篇：中缀表达式转后缀表达式 与 表达式树

知识导航

• 一.背景分析：
• 二.中缀表达式转化为后缀表达式
• 三.后缀表达式构建表达式树

---

一.背景分析：

表达式树是由运算符与 *** 作数组建而成的一颗树（不一定是二叉树），表达式树的树叶为 *** 作数，如常数或者变量名，而其他节点为 *** 作符。如下
就是一颗表达式树：
根据表达式树的前序遍历，中序遍历，后序遍历，我 们分别可以得出常见的三种表达式，前缀表达式，中缀表达式与后缀表达式，
前缀表达式：++abc+defg
后缀表达式：abc+def+g+
中缀表达式：（a+b * c）+((d*e+f)*g)

二.中缀表达式转化为后缀表达式

在这里我们尝试将中缀表达式转化为后缀表达式
以a+b * c+(d * e+f)*g为例：
转化规则：
1.确立各个字符的优先级： 左右括号 > * / > + -
2.我们可以用一个栈来存储运算符，用一个list来存储输出的值
2.当扫描到左右括号直接入栈，扫描到的是运算符则分为两种情况：
（1）栈顶 *** 作符的优先级小于当前运算符优先级时或者运算符栈为空(如+和-的优先级低于 * 和 /)，直接入栈。
（2）栈顶 *** 作符的优先级大于或等于当前运算符优先级且运算符不为空时，循环执行出栈 *** 作并加入list中，直到遇到优先级小于当前运算符的元素为止。循环执行完后再将当前运算符压栈。特别注意的是，只有遇到右括号时，左括号才出栈
（3）在进行符号 *** 作时吗，只有遇到右括号，左括号才会出栈。当遇到右括号循环执行出栈 *** 作，只到左括号被d出。特别注意：不管是右括号还是d出的左括号都不执行输出 *** 作。
下面我们就来进行转化演示:
a+b * c+(d * e+f)*g
一开始读到a直接输出，然后是+运算符（此时栈为空）直接入栈。
然后直接将b 入栈，接着扫描到 *，因为+的运算符低于 的运算符，所以 * 直接入栈，紧接着c直接入栈。
接着扫描到了‘+’运算符，因为‘’运算符比‘+’运算符的优先级高，所以循环执行出栈 *** 作，直到运算符优先级小于‘+’。由于’+'的运算符优先级等于‘+’，所以栈内运算符都被d出，‘扫描到的+’入栈。
然后遇到左括号，直接入栈。输出d，由于‘（ ’括号只有遇到右括号时才会出栈，
所以将 * 入栈。e直接输出

然后扫描遇到‘+’号，乘号的运算级高于’+‘号，所以称号直接d出栈输出,’+'号入栈。f 直接入栈
接着遇到右括号，循环执行出栈 *** 作，知道左括号出栈（注意左括号不执行输出）

然后乘号入栈，输出g
最后将剩余元素d出栈，输出
至此中缀表达式就转化成了后缀表达式

代码演示

public class mum{
    private static int proTest(Character a1){
        if(a1.equals('*')||a1.equals('/'))
        {
            return 1;
        }else if(a1.equals('+')||a1.equals('-')){
            return 0;
        }else{//只能是括号了
            return 2;
        }
    }

    public static void main(String[] args) {
        String str="a+b*c+(d*e+f)*g";
        Stack<Character> stack=new Stack<>();
        List<Character> list=new ArrayList<>();
        Character a;
        //将字符串转化吧为字符数组便于进行 *** 作
        char[] nums=str.toCharArray();
        for (int i = 0; i <nums.length ; i++) {
            char res=nums[i];
            if(Character.isLetterOrDigit(res)){
               list.add(res);
            }else if(nums[i]=='('){
            stack.push(res);
            }else if(nums[i]==')'){
                //如果是右括号则一直出栈，加入到输入的list中，直到左括号出栈
                while(!stack.isEmpty()) {
                    Character c = stack.pop();
                    if (c == '(') {
                        break;
                    }
                    list.add(c);
                }
            }else{//到这里只能是运算符了
                //虽然一开始肯定会有一个数字或者字母入栈，但是也有可能在之前的 *** 作中已经出栈完了
                if(stack.isEmpty()){
                    stack.push(res);
                }else {
                    Character ret = stack.peek();
                    while (!stack.isEmpty()&&proTest(ret) >= proTest(res)) {
                        a = stack.peek();
                        if(a!='(') {
                            list.add(stack.pop());
                        }else{
                            break;
                        }
                    }
                    stack.push(res);
                }
            }

        }
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }

        System.out.println(list);


    }


}

结果验证：

三.后缀表达式构建表达式树

我们上面已经掌握了中缀表达式转化为后缀表达式，下面我们来聊一聊后缀表达式转化为表达式树的逻辑。其实逻辑并不难。同样是借助一个栈，然后对表达式进行扫描，如果扫描到是是数字或者字符则直接入栈，如果扫描到的是运算符，则d出栈顶两个元素，重新构造二叉树。重复执行上述 *** 作。

代码实现

import printer.BinaryTreeInfo;
import printer.BinaryTrees;

import java.util.Scanner;
import java.util.Stack;

class TreeNode{
char val;
TreeNode left;
TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}

public class Operator {
    public static void main(String[] args) {
        Stack<TreeNode>stack=new Stack<>();
        Scanner scan=new Scanner(System.in);
        String str=scan.nextLine();
        char [] ret=str.toCharArray();
        for (int i = 0; i <ret.length; i++) {
            char c=ret[i];
            if(Character.isLetterOrDigit(c)){
                stack.push(new TreeNode(c));
            }else {
                //后序表达式只有运算符和 *** 作数两种情况，没有左右括号
                TreeNode cur1=stack.pop();
                TreeNode cur2=stack.pop();
                TreeNode node=new TreeNode(c);
                stack.push(node);
                node.left=cur2;
                node.right=cur1;
            }

        }
        //二叉树打印方法
        TreeNode res=stack.pop();
        BinaryTrees.println(new BinaryTreeInfo() {
            @Override
            public Object root() {
                return res;
            }

            @Override
            public Object left(Object node) {
                return ((TreeNode)node).left;
            }

            @Override
            public Object right(Object node) {
                return  ((TreeNode)node).right;
            }

            @Override
            public Object string(Object node) {
                return ((TreeNode)node).val;
            }
        });

    }
}

结果测试
二叉树打印工具可以去我的代码仓库看看：二叉树打印