Java实现逆波兰表达式的计算（含中缀转后缀）

男娘i 2022-11-19 11:27 204阅读 0赞

Java实现逆波兰表达式的计算  
1.心得  
逆波兰表达式的计算是栈的典型应用。栈的最大特点就是，先进后出；即先压入栈的元素最后出，而后入栈的元素先出栈。栈的常规操作有，压栈push，弹栈pop，返回栈顶元素peek等。其实，在前缀，中缀，后缀模拟计算器计算中，后缀表达式对于计算机来说是最容易的。而且三者中，代码实现起来也是比较容易的。比如，后缀在计算时，只需要用到一个栈。而中缀计算需要两个栈来完成。

2.思路分析  
一、首先将中缀表达式（String）的数和操作符依次分开存入集合中。

要点
    	1.需要创建一个集合
    	2.取数时，需要注意多位数的情况

二、将存入集合的中缀表达式再转换成后缀表达式

要点
    1.需要两个栈；在本代码中，由于栈的出栈顺序，我们需要将存放后缀表式的栈再逆序输出才能得到正确的结果，所以为了简化，建立一个栈s1存放运算符，而用集合s2来存放数和s1弹出的元素
    2.扫描中缀表达式集合，
    	2.1 当遇到数时，直接入栈s2（集合），
    	2.2 当遇到运算符时：
    		如果栈空，直接入栈s1；
    		如果是“（”，直接入栈s1；
    		如果是“）”，则依次弹栈s1，并将弹出的元素add进s2，直到遇到“（ "时，将“（”弹出，即消除一对"（）"
    		如果当前扫描到的运算符优先级 <= s1栈顶运算符的优先级，则依次弹栈s1，并将弹出的元素add进s2中，直到当前扫描到的运算符优先级 >= s1栈顶运算符的优先级;再将当前运算符压栈s1中
    	3.当扫描完中缀表达式集合，s1栈还有元素，则依次弹栈存入s2中

三、将后缀表达式集合进行计算

要点
    1.需要一个栈
    2.遍历后缀表达式集合
    	2.1当遇到数，直接入栈
    	2.2 当遇到操作符，则弹出两个元素进行计算，将结果入栈
    	2.3最好栈内的元素即为后缀表达式计算结果

3.代码实现

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public static void main(String[] args){
        
    		String infixExper = "1+((2+3)*4)-5";  //[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
            List<String> list = perserverToList(infixExper);
            System.out.println(list);
            List<String> list2 = infixToSuffix(list);
            System.out.println(list2);  //[1, 2, 3, +, 4, *, +, 5, -]
            int res = calculate(list2);
            System.out.println(res);
    			
    			
    	}
    	
    	
    	//第一步 将infixExper存到集合中，便于遍历转成后缀
    	public static List<String> perserverToList(String exp){
        
    		
    		List<String> list = new ArrayList<>();
    		String str = "";
    		
    		for(int i = 0;i < exp.length();){
        	
    			char ch = exp.charAt(i);
    			//如果是操作符直接入集合
    			if(ch < 48 || ch > 57){
        
    				list.add(ch + "");
    				i++;                   //重点
    			}else{
        
    				//如果是数字（或者多位数），那么拼接并入集合
    				str = "";   //当该读入下一个数字时，需要置空上次的内容
    				while(i < exp.length() && exp.charAt(i) >= 48 && exp.charAt(i) <= 57){
        
    					str += ch;
    					i++;
    				}
    				list.add(str);
    			}
    		}
    		return list;
    	}
    	
    	//第二步：将分好的中缀表达式集合——>后缀表达式集合
    	public static List<String> infixToSuffix(List<String> list){
        
    		
    		//栈s1用来存放读取的数字，以及s2弹栈的操作符
    		//s2用来存放操作符
    		List<String> s1 = new ArrayList<>();
    		Stack<String> s2 = new Stack<>();
    		
    		for(String ele : list){
        
    			
    			if(ele.matches("\\d+")){
          //"\\d+"正则表达式，表示多位数
    				s1.add(ele);
    			}else if(ele.equals("(")){
        
    				
    				s2.push(ele);
    				
    			}else if(ele.equals(")")){
         //如果扫描到），则s2不断弹出并存入s1,直到遇到（
    				
    				while(s2.size() != 0 && !s2.peek().equals("(")){
        
    					s1.add(s2.pop());
    					
    				}
    				//遇到（，使（）消失
    				s2.pop();
    			}else{
        
    				//遇到操作符，根据优先级入栈弹栈
    				//一定s2.size在前，否则EmptyStackException
    				//原因：当栈空时，s2.peek（）看栈顶元素会出错
    				while(s2.size() > 0 && priority(ele) <= priority(s2.peek())){
        
    					
    					s1.add(s2.pop());
    					
    				}
    				s2.push(ele);		
    			}	
    		}
    		//当扫描完后缀集合，s2栈内还有操作符，则依次弹出，并存入s1
    		while(s2.size() != 0){
        
    			
    			s1.add(s2.pop());
    		}
    	return s1;
    	}
    	
    	//定义优先方法
    	public static int priority(String op){
        
    		
    		int pr = 0;
    		if(op.equals("+")){
        
    			pr = 1;
    		}
    		if(op.equals("-")){
        
    			pr = 1;
    		}
    		if(op.equals("*")){
        
    			pr = 2;
    		}
    		if(op.equals("/")){
        
    			pr = 2;
    		}
    		return pr;
    	}
    	
    	//第三步：将后缀的集合进行计算
    	public static int calculate(List<String> ls){
        
    		
    		//根据原理，该过程只需用到一个栈存放数字及结果
    		
    		Stack<Integer> num = new Stack<>();
    		
    		for(String ele : ls){
        
    			
    			//当遇到数字，直接入栈
    			if(ele.matches("\\d+")){
        
    				
    				num.push(Integer.parseInt(ele));
    			}else{
        
    				//遇到操作符直接弹数栈计算，并将结果保存到数栈
    					int num1 = num.pop();
    					int num2 = num.pop();
    					int res = 0;
    					res = auxiliary(num1,num2,ele);
    					num.push(res);
    			}
    		}
    		return num.pop();
    	}
    	
    	//根据操作符计算结果
    	public static int auxiliary(int num1,int num2,String op){
        
    		int res = 0;
    		if(op.equals("+")){
        
    			res = num1 + num2;
    			
    		}
    		if(op.equals("*")){
        
    			res = num1 + num2;
    			
    		}
    		if(op.equals("-")){
        
    			res = num2 + num1;
    			
    		}
    		if(op.equals("/")){
        
    			res = num2 + num1;
    			
    		}
    		return res;
    	}