中缀表达式转后缀表达式并计算结果

不念不忘少年蓝@ 2022-09-30 06:23 186阅读 0赞

测试数据要求：非负整型数，支持包含括号的四则运算

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class Postfix {
    	public static void main(String[] args) {
    		Scanner sr = new Scanner(System.in);
    		Queue postfix = getPostfix(sr.next());
    		int result = getResult(postfix);
    		System.out.println(result);
    	}
    
    	/**
    	 * 
    	 * @param postfix 后缀表达式在队列中的形式
    	 * @return 后缀表达式的计算结果
    	 */
    	private static int getResult(Queue postfix) {
    		Stack<Integer> numbers = new Stack<Integer>();
    		while(!postfix.isEmpty()){ 
    			Object temp = postfix.poll();
    			//判断temp类型，如果是Integer就入栈，如果是Character就进行运算
    			if(temp instanceof Integer)
    				numbers.push((Integer)temp);
    			else{
    				//先出栈的是操作数B
    				int numB = numbers.pop();
    				int numA = numbers.pop();
    				switch ((Character)temp) {
    				case '+':
    					numA += numB;
    					break;
    				case '-':
    					numA -= numB;
    					break;
    				case '*':
    					numA *= numB;
    					break;
    				case '/':
    					numA /= numB;
    					break;
    				}
    				//最后记得将运算结果入栈
    				numbers.push(numA);
    			}
    		}
    		//返回运算结果（栈底）
    		return numbers.get(0);
    	}
    
    	/**
    	 * 
    	 * @param ss 中缀表达式
    	 * @return 后缀表达式在队列中的形式
    	 */
    	private static Queue getPostfix(String ss) {
    		Stack<Character> ops = new Stack<Character>();
    		Queue<Object> postfixs = new LinkedList<Object>();
    		for(int i=0;i<ss.length();i++){
    			char temp = ss.charAt(i);
    			//1.如果是数字就加入队列
    			if(Character.isDigit(temp)){
    				int number = 0;
    				//数字拼接
    				while(i < ss.length() && Character.isDigit(ss.charAt(i))){
    					number = number*10 + Integer.parseInt(ss.substring(i,i+1));
    					i++;
    					
    				}
    				//i多加了一次，记得减掉
    				i--;
    				postfixs.offer(number);
    			}
    			//2.如果是'('就入栈
    			else if(temp == '(')
    				ops.push(temp);
    			//3.如果是')'就出栈并加入队列直到'('出栈，其中'('只出栈不加入队列
    			else if(temp == ')'){
    				char popChar = ops.pop();
    				while(popChar != '('){
    					postfixs.offer(popChar);
    					popChar = ops.pop();
    				}
    			}
    			//4.如果是操作符的逻辑处理
    			else{
    				int rank = getRank(temp);
    				//4.1.如果栈空或者权值比栈中前一个操作符权值大，则入栈
    				if(ops.isEmpty() || rank > getRank(ops.peek()))
    					ops.push(temp);
    				//4.2.1否则出栈，直到栈空或者权值比栈中前一个操作符权值大
    				else {
    					while(!ops.isEmpty() && rank <= getRank(ops.peek()))
    						postfixs.offer(ops.pop());
    					//4.2.2最后记得将当前操作符入栈
    					ops.push(temp);
    				}
    			}
    		}
    		//5.将堆栈中剩余操作符加入队列
    		while(!ops.isEmpty())
    			postfixs.offer(ops.pop());
    		return postfixs;
    	}
    	
    	/**
    	 * 
    	 * @param c 字符
    	 * @return 输入字符的权值
    	 */
    	private static int getRank(char c){
    		switch (c) {
    		case '+':
    		case '-':
    			return 1;
    		case '*':
    		case '/':
    			return 2;
    		}
    		return -1;
    	}
    }

示例：

![SouthEast][]

[SouthEast]: /images/20220708/2d2da8a433d940baa603e54ac72d49fa.png