基于Java实现逆波兰（后缀）表达式计算

偏执的太偏执、 2023-01-06 14:59 163阅读 0赞

一、逆波兰（后缀）表达式计算

1.逆波兰表达式，又叫做后缀表达式。什么是逆波兰表达式呢？逆波兰表达式其实是 “操作数写在前面,操作符写在后面”。  
比如：3 4 + 5 \* 6 -

2.算法描述：  
1.）对该表达式扫描，出现的情况就两种，即数字和操作符  
2.）如果是数，那么直接入栈  
3.）如果是操作符，则弹出两个数，并对其进行计算，再将结果入栈  
4.)弹栈计算时，注意操作数的位置，例如：后弹栈的数作被除数，先弹栈的作除数；减法类似

重复以上操作，直到扫描结束，栈中最后保存的结果即为表达式结果，弹栈

3.代码  
代码思路：  
本代码是基于已有栈进行：  
a.首先将表达式进行分割，并保存到集合中；通过集合的遍历完成入栈，计算操作  
b.由于集合中的数据类型是String,所以对数计算需要String->Integer的转换  
c.这里 判断数的条件是通过 正则表达式 “\\\\d+” 完成的

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class suffixCalculate {
        
    
        public static void main(String[] args){
        
    
            String expression= "3 4 + 5 * 6 -";
    
            List<String> list = spiltExpression(expression);
            int result = calculate(list);
            System.out.println("result="+result);
        }
    
        public static List<String> spiltExpression(String experssion){
        
    
            String[] str = expression.split(" ");
            List<String> list = new ArrayList<>();
    
            for(String ele : str){
        
                list.add(ele);
            }
            return list;
    
        }
    //将表达式分割成String[] 保存到集合的方法
        public static int calculate(List<String> list){
        
    
    
            Stack<Integer> numStack = new Stack<>();
    //遍历集合  可用增强 for循环 （for each）
            for(String item : list){
        
    
                if(item.matches("\\d+")){
        
    
                    numStack.push(Integer.parseInt(item));
                }else{
        
                    //如果是符号则弹数计算并存结果
                    int num1 = numStack.pop();
                    int num2 = numStack.pop();
                    int res = 0;
                    res = calcu(num1,num2,item);
                    numStack.push(res);
                }
            }
            return numStack.pop();
        }
    //计算的方法
        public static int calcu(int num1,int num2,String op){
        
            int res = 0;
            if(op.equals("*")){
        
    
                 res = num1 * num2;
            }
            if(op.equals("/")){
        
    
                 res = num2 / num1;
            }
            if(op.equals("+")){
        
    
                 res = num1 + num2;
            }
            if(op.equals("-")){
        
    
                 res = num2 - num1;
            }
    
            return res;
        }
    
    }