java计算后序表达式
简介
题目要求如下:
用二叉树读取前缀表达式,打印该算式的后缀表达式,并求解
代码实现
TreeNode类:
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类:
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;
}
}
主函数
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();
}
}