基于二叉树的表达式求值算法

本文记录数据结构习题解析与实验指导（李冬梅）的课后实验六——基于二叉树的表达式求值算法

1 实验内容

没有找到实验的文字版本，只能把实验书的图片放上来了😅

2 基本思路

其实思路和中缀算术表达式求值这篇文章是一样的。两个栈，一个存操作符，一个存结果，只不过这次存结果的栈要改成存树。于是入栈就要改成这样：
遇到数字：

if (data[i] >= '0' && data[i] <= '9') {
                Tree t = new Tree();
                t.ans = data[i] - 48;
                stack1.push(t);
            }

需要计算时：

public void calculate2(char c) {
        Tree t1, t2, t3;
        switch (c) {
        case '+':
            t1 = stack1.pop();
            t2 = stack1.pop();
            t3 = new Tree(t2, t1);
            t3.oper = '+';
            stack1.push(t3);
            break;
        case '-':
            t1 = stack1.pop();
            t2 = stack1.pop();
            t3 = new Tree(t2, t1);
            t3.oper = '-';
            stack1.push(t3);
            break;
        case '*':
            t1 = stack1.pop();
            t2 = stack1.pop();
            t3 = new Tree(t2, t1);
            t3.oper = '*';
            stack1.push(t3);
            break;
        case '/':
            t1 = stack1.pop();
            t2 = stack1.pop();
            t3 = new Tree(t2, t1);
            t3.oper = '/';
            stack1.push(t3);
            break;
        }
    }

然后都结束后，我们的存树的栈的栈顶数据就会是二叉树的根节点。

然后，我们从根节点出发，利用递归，来求值。

    public int getValue(char c, int lValue, int rValue) {
        switch(c) {
        case '+':
            return lValue + rValue;
        case '-':
            return lValue - rValue;
        case '*':
            return lValue * rValue;
        case '/':
            return lValue / rValue;
        }
        return -1;
    }

    public int evaluateExpTree(Tree t) {
        int lValue, rValue;
        if (t.left == null && t.right == null) {
            return t.ans;
        } else {
            lValue = evaluateExpTree(t.left);
            rValue = evaluateExpTree(t.right);
            return getValue(t.oper, lValue, rValue);
        }
    }

3 全部代码

import java.util.Stack;

class Tree {
    char oper;
    int ans;
    Tree left;
    Tree right;

    public Tree() {

    }

    public Tree(Tree left, Tree right) {
        this.left = left;
        this.right = right;
    }
}


class ExpressionCalculate {
    private Stack<Tree> stack1;
    private Stack<Character> stack2;
    private char[] data;

    public ExpressionCalculate(String s) {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
        data = s.toCharArray();
    }

    public int getPriority(char c) {
        int priority = 0;
        if (c == '#') {
            priority = 3;
        } else if (c == '*' || c == '/') {
            priority = 2;
        } else if (c == '+' || c == '-') {
            priority = 1;
        } else if (c == '(') {
            priority = 0;
        }
        return priority;
    }

    public void calculate2(char c) {
        Tree t1, t2, t3;
        switch (c) {
        case '+':
            t1 = stack1.pop();
            t2 = stack1.pop();
            t3 = new Tree(t2, t1);
            t3.oper = '+';
            stack1.push(t3);
            break;
        case '-':
            t1 = stack1.pop();
            t2 = stack1.pop();
            t3 = new Tree(t2, t1);
            t3.oper = '-';
            stack1.push(t3);
            break;
        case '*':
            t1 = stack1.pop();
            t2 = stack1.pop();
            t3 = new Tree(t2, t1);
            t3.oper = '*';
            stack1.push(t3);
            break;
        case '/':
            t1 = stack1.pop();
            t2 = stack1.pop();
            t3 = new Tree(t2, t1);
            t3.oper = '/';
            stack1.push(t3);
            break;
        default:
            break;
        }
    }

    public void calculate(char c) {
        char t;
        if (c == ')') {
            t = stack2.pop();
            while (t != '(') {
                calculate2(t);
                t = stack2.pop();
            }
        } else {
            t = stack2.pop();
            int p1 = getPriority(c);
            int p2 = getPriority(t);
            while (p2 >= p1) {
                calculate2(t);
                if (stack2.empty()) {
                    break;
                }
                t = stack2.pop();
                p2 = getPriority(t);
            }
            if (p2 < p1) {
                stack2.push(t);
            }
            stack2.push(c);
        }
    }

    public int getValue(char c, int lValue, int rValue) {
        switch(c) {
        case '+':
            return lValue + rValue;
        case '-':
            return lValue - rValue;
        case '*':
            return lValue * rValue;
        case '/':
            return lValue / rValue;
        default:
            break;
        }
        return -1;
    }

    public int evaluateExpTree(Tree t) {
        int lValue, rValue;
        if (t.left == null && t.right == null) {
            return t.ans;
        } else {
            lValue = evaluateExpTree(t.left);
            rValue = evaluateExpTree(t.right);
            return getValue(t.oper, lValue, rValue);
        }
    }

    public void proceed() {
        for (int i = 0; i < data.length; ++i) {
            if (data[i] >= '0' && data[i] <= '9') {
                Tree t = new Tree();
                t.ans = data[i] - 48;
                stack1.push(t);
            } else if (data[i] == '(') {
                stack2.push(data[i]);
            }  else if (data[i] == ')') {
                calculate(data[i]);
            } else {
                if (stack2.empty()) {
                    stack2.push(data[i]);
                } else {
                    int p1 = getPriority(data[i]);
                    int p2 = getPriority(stack2.peek());
                    if (p1 > p2) {
                        stack2.push(data[i]);
                    } else {
                        calculate(data[i]);
                    }
                }
            }
            if (i == data.length - 1) {
                if (stack2.empty()) {
                    System.out.println(stack1.pop());
                } else {
                    while (!stack2.empty()) {
                        char c = stack2.pop();
                        calculate2(c);
                    }
                }
            }
        }

        System.out.println(evaluateExpTree(stack1.pop()));
    }

}

public class Test2 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String test = "(3*5+3)/6+5+3*4";
        ExpressionCalculate e = new ExpressionCalculate(test);
        e.proceed();
    }

}

到这里这篇文章就结束了。如果有错误，可以在下方评论，或者私聊我😉，我会及时改正的。

如果看了有收获，可以点赞加关注😉，看计算机小白的成长之路。