java数据结构和算法——后缀表达式（即逆波兰表达式）计算器（即求值）

一、逆波兰表达式求值思路分析

• 定义一个逆波兰表达式，例如：(3+4)*5-6的逆波兰表达式为 3 4 + 5 * 6 -

• 将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList中

• 完成对逆波兰表达式的运算步骤如下：

  1）、从左至右扫描，将3和4压入堆栈； 2）、遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈； 3）、将5入栈； 4）、接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 5）、将6入栈； 6）、最后是-运算符，计算出35-6的值，即29，由此得出最终结果

二、逆波兰表达式求值代码示例

1、代码

package com.rf.springboot01.dataStructure.stack.reversePolishNotation;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @description: 逆波兰表达式计算器
 * @author: xiaozhi
 * @create: 2020-07-28 23:03
 */
public class ReversePolishCalculator {
    public static void main(String[] args) {
        //定义一个逆波兰表达式 例如：(3+4)*5-6的逆波兰表达式为 3 4 + 5 * 6 -
        String suffixExpression="3 4 + 5 * 6 -";
        List listStr=getList(suffixExpression);
        System.out.println(listStr);
        int res=computer(listStr);
        System.out.println("计算的结果为："+res);

    }
    
    //将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList中
    public static List getList(String str){
        List list=new ArrayList();
        String[] split = str.split(" ");
        for(String item:split){
            list.add(item);
        }
        return list;
    }

    /**
    * @Description:  完成对逆波兰表达式的运算
     *      1)从左至右扫描，将3和4压入堆栈；
     * 		2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
     * 		3)将5入栈；
     * 		4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
     * 		5)将6入栈；
     * 		6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
    * @Param:
    * @Author: xz
    * @return:
    * @Date: 2020/7/28 23:10
    */
   public static int computer(List list){
       // 创建给栈, 只需要一个栈即可
       Stack stack =new Stack();
       //遍历
       for(String data:list){
            if(data.matches("\\d+")){//匹配的是多位数
                stack.push(data);//入栈
            }else{//是符号，先pop出两个数，并运算，再入栈
                int num2=Integer.parseInt(stack.pop());
                int num1=Integer.parseInt(stack.pop());
                int result=0;
                if(data.equals("+")){
                    result=num1+num2;
                }else if(data.equals("-")){
                    result=num1-num2;
                }else if(data.equals("*")){
                    result=num1*num2;
                }else if(data.equals("/")){
                    result=num1/num2;
                }else{
                    throw new RuntimeException("运算符有误");
                }
                //把结果result转字符串后入栈
                stack.push(result+"");
            }
       }
        //最后留在stack中的数据是运算结果
        return  Integer.parseInt(stack.pop());
   }
}

2、运行main方法测试，输出结果如下