Loading... # java计算后序表达式 ## 简介 题目要求如下: 用二叉树读取前缀表达式,打印该算式的后缀表达式,并求解  ## 代码实现 **TreeNode类:** ```java package com.zbl; /** * @Author {zbl} * @Date: 2019/12/09/ 12:15 * @Description */ public class TreeNode<T> { public T data; public TreeNode left; public TreeNode right; TreeNode(T data){ this.data = data; } } ``` **BiTree类:** ```java package com.zbl; import java.util.LinkedList; import java.util.Queue; /** * @Author {zbl} * @Date: 2019/12/09/ 11:54 * @Description */ public class BiTree<T> { //根结点 protected TreeNode<T> root; protected Queue<T> queue; //构造函数 public BiTree(LinkedList<T> inputList){ root = this.creatBiTree(inputList); queue = new LinkedList<T>(); } //添加结点 public TreeNode creatBiTree(LinkedList<T> inputList){ TreeNode<T> tmp = null; //判空 if(inputList==null || inputList.size()==0) return null; //存值 T data = inputList.removeFirst(); if(data != null){ tmp = new TreeNode(data); tmp.left = this.creatBiTree(inputList); tmp.right = this.creatBiTree(inputList); } //返回根结点 return tmp; } public void PostOrder(){ this.PostOrder(this.root); //换行 System.out.println(); } //后续遍历 protected void PostOrder(TreeNode<T> node){ if(node != null){ PostOrder(node.left); PostOrder(node.right); System.out.print(node.data + " "); //入队 queue.add(node.data); } } public Queue<T> getQueue() { return this.queue; } } ``` **主函数** ```java package com.zbl; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; /** * @Author {zbl} * @Date: 2019/12/09/ 11:54 * @Description */ public class Main { // 前序表达式+-+*3..*1..1..1../1..1..5.. public static void main(String[] args) { // write your code here Scanner scan = new Scanner(System.in); System.out.println("请输入前缀表达式:"); String str =scan.next(); LinkedList<Character> list = new LinkedList<>(); for (int i = 0; i <str.length() ; i++) { char c = str.charAt(i); if(c=='.') list.add(null); else list.add(c); } BiTree<Character> tree = new BiTree<>(list); //后续遍历 tree.PostOrder(); //求解 System.out.println(solve(tree)); } public static Double solve(BiTree<Character> tree){ //获取后续表达式 Queue<Character> queue = tree.getQueue(); //数值栈 Stack<Double> num = new Stack<>(); //若栈不为空 while(!queue.isEmpty()){ char x = queue.poll(); if(x >= '0' && x <= '9'){ int tmp = x-'0'; num.push(new Double(tmp)); } //弹栈计算新值,并将新值入栈 else{ //此处注意数值先后顺序 double b = num.pop(); double a = num.pop(); double result = 0; switch (x){ case '+': result = a + b;break; case '-': result = a - b;break; case '*': result = a * b;break; case '/': result = a / b;break; } num.push(result); } } return num.pop(); } } ``` 最后修改:2020 年 02 月 27 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏