数据结构程序设计——使用栈和二叉树对中缀表达式求值
实验须知：
实验目的： 熟练掌握二叉树的构造和遍历方法。
实验内容 ：我们通常所见的算术表达式为中缀表达式，对其进行计算时，须根据运算优先级并按照从 左到右的顺序来进行。对于计算机来说，直接对中缀表达式进行计算比较困难，而对后缀表达式进行 计算较为容易。
那么如何将中缀表达式转换为后缀表达式呢？首先借助于二叉树和栈由给定的中缀表达式创建二叉树，然后对二叉树进行后序遍历得到后缀表达式。
实验要求：
（ 1 ）用户输入一个中缀表达式 “3+2*9-6/2” ；
（ 2 ）由该中缀表达式非递归创建一棵二叉树；
（ 3 ）非递归后序遍历该二叉树得到后缀表达式；
（ 4 ）借助栈对这一后缀表达式求值并将结果输出。
【实验提示】
（ 1 ）输入中缀表达式时（按回车键结束输入），建议以空格分隔操作数与运算符，以便于处理。
（ 2 ）需验证由 “3+2*9-6/2” 转换的后缀表达式是否正确。
（ 3 ）进行除法运算时，需对除数为 0 的情况做异常处理。
代码实现：
import java.util.Scanner;
import java.util.Stack;class TreeNodes {char val;TreeNodes left, right;public TreeNodes(char val) {this.val = val;this.left = this.right = null;}
}public class ExpressionTree {public static boolean isOperator(char c) {return c == '+' || c == '-' || c == '*' || c == '/';}public static int getPriority(char c) {if (c == '+' || c == '-') {return 1;} else if (c == '*' || c == '/') {return 2;}return 0;}public static TreeNodes buildExpressionTree(String expression) {Stack<TreeNodes> nodeStack = new Stack<>();Stack<Character> opStack = new Stack<>();for (char c : expression.toCharArray()) {if (Character.isDigit(c)) {nodeStack.push(new TreeNodes(c));} else if (isOperator(c)) {while (!opStack.isEmpty() && getPriority(opStack.peek()) >= getPriority(c)) {TreeNodes right = nodeStack.pop();TreeNodes left = nodeStack.pop();TreeNodes operatorNode = new TreeNodes(opStack.pop());operatorNode.left = left;operatorNode.right = right;nodeStack.push(operatorNode);}opStack.push(c);}}while (!opStack.isEmpty()) {TreeNodes right = nodeStack.pop();TreeNodes left = nodeStack.pop();TreeNodes operatorNode = new TreeNodes(opStack.pop());operatorNode.left = left;operatorNode.right = right;nodeStack.push(operatorNode);}return nodeStack.isEmpty() ? null : nodeStack.pop();}public static void postOrderTraversal(TreeNodes root) {if (root != null) {postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val + " ");}}public static int evaluateExpression(TreeNodes root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return root.val - '0';}int leftEval = evaluateExpression(root.left);int rightEval = evaluateExpression(root.right);switch (root.val) {case '+':return leftEval + rightEval;case '-':return leftEval - rightEval;case '*':return leftEval * rightEval;case '/':return leftEval / rightEval;default:return 0;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.print(" ʽ ");String infixExpression = scanner.nextLine();String[] tokens = infixExpression.split(" ");StringBuilder postfixExpression = new StringBuilder();for (String token : tokens) {postfixExpression.append(token);postfixExpression.append(" ");}System.out.println(" ʽ " + infixExpression);TreeNodes root = buildExpressionTree(infixExpression);System.out.print(" ʽ ");postOrderTraversal(root);System.out.println();int result = evaluateExpression(root);System.out.println(" " + result);scanner.close();}
}有需要的自取~~