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

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

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();
	}

}

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

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