java计算后序表达式

admin123

2019 年 12 月 09 日

2943 次浏览

1 条评论

加载中

2348字数

代码相关

# java计算后序表达式
## 简介
题目要求如下：
用二叉树读取前缀表达式，打印该算式的后缀表达式，并求解
![TIM截图20191209141430.png](/usr/uploads/2019/12/2424411111.png)

## 代码实现
**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();
    }
}
```

java计算后序表达式