Java用栈实现中缀表达式转逆波兰表达式（后缀表达式）并计算结果

比眉伴天荒 2023-07-10 08:52 92阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

算法支持加、减、乘、除、括号的计算，并且支持小数。  
字符之前要用一个空格间隔。

import java.util.Stack;
    import java.math.BigDecimal;
    
    public class RPN {
        
    	/**
    	 * 优先级比较
    	 * @param s 传入运算符
    	 * @return 返回运算符的优先级
    	 */
    	public static int priority(String s) {
        
    		switch(s) {
        
    		case "(": return 1; //保证"("后的第一个运算符入栈
    		case ")": return 1;
    		case "+": return 2;
    		case "-": return 2;
    		case "*": return 3;
    		case "/": return 3;
    		default: throw new RuntimeException("operator error!");
    		}
    	}
    	
    	/**
    	 * 中缀表达式转换为后缀表达式, 各单位间用空格间隔
    	 * @param str  中缀表达式
    	 * @return 逆波兰表达式（后缀表达式）
    	 */
    	public static String midToRPN(String str) {
        
    		String result = "";
    		int k = 0;//保证第一个运算符入栈
    		Stack<String> stack = new Stack<String>();
    		String[] s = str.split(" ");
    		for(int i=0; i<s.length; i++) {
        
    			if(isNumber(s[i])) {
        //数值直接输出
    				result += s[i] +" ";
    			}else {
        //如果是运算符
    				if(!stack.isEmpty()) {
        //获得栈顶运算符优先级
    					k = priority(stack.peek());
    				}
    				if(priority(s[i]) > k || s[i].equals("(")) {
        //当前运算符优先级高于栈顶，压栈
    					stack.push(s[i]);
    				}else {
        //否则取出栈里的元素直到遇到"("或栈空
    					while(!stack.isEmpty()) {
        
    						if(stack.peek().equals("(")) {
        
    							stack.pop();
    							break;
    						}
    						result += stack.pop() + " ";
    					}
    					if(!s[i].equals(")")){
         //如果不是")"， 压栈,右括号不需要压栈
    						stack.push(s[i]);
    					}
    				}
    			}
    		}
    		while(!stack.isEmpty()) {
        //最后取出栈里的运算符
    			result += stack.pop() + " ";
    		}
    		return result;
    	}
    	//判断字符是不是数字
    	public static boolean isNumber(String str) {
         
            if(str.equalsIgnoreCase("+") || str.equalsIgnoreCase("-") || str.equalsIgnoreCase("*") || 
            		str.equalsIgnoreCase("/") || str.equalsIgnoreCase("(") || str.equalsIgnoreCase(")")) {
        
            	return false;
            }
            return true; 
    	}
    	
    	/**
    	 * 计算结果
    	 * @param n1 第一个参数
    	 * @param n2 第二个参数
    	 * @param c 运算符
    	 * @return 结果
    	 */
    	public static BigDecimal calculation(BigDecimal n1, BigDecimal n2, String c) {
        
    		switch(c) {
        
    		case "+": return n1.add(n2);
    		case "-": return n1.subtract(n2);
    		case "*": return n1.multiply(n2);
    		case "/": return n1.divide(n2,2,BigDecimal.ROUND_HALF_UP);
    		default: throw new RuntimeException("Error!");
    		}
    	}
    	
    	/**
    	 * 计算后缀表达式得出结果, 中间以空格为间隔, 使用BigDecimal保证精度
    	 * @param str 后缀表达式
    	 * @return 计算结果
    	 */
    	public static BigDecimal RPNtoResult(String str) {
        
    		BigDecimal result;
    		Stack<BigDecimal> stack = new Stack<BigDecimal>();
    		String[] s = str.split(" ");
    		
    		for(int i=0; i<s.length; i++) {
        
    			if(isNumber(s[i])) {
        
    				stack.push(new BigDecimal(s[i]));
    			}else {
        
    				BigDecimal n2 = stack.pop();
    				BigDecimal n1 = stack.pop();
    				BigDecimal temp = calculation(n1, n2, s[i]);
    				stack.push(temp);
    			}
    		}
    		System.out.println("result:" + stack.peek());
    		result = stack.pop();
    		return result;
    	}
    	
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    
    		RPNtoResult(midToRPN("10 / 5 * 5 / ( ( 1 + 3 ) - 2 )"));
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982