LQOJ ALGO-156 表达式计算

╰+攻爆jí腚メ 2022-06-17 01:45 117阅读 0赞

# **表达式计算** #

**问题描述**

输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。

**输入格式**  
　　  
输入一行，包含一个表达式。

**输出格式**

输出这个表达式的值。

**样例输入**

> 1-2+3\*(4-5)

**样例输出**

> \-4

**数据规模和约定**

表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

**解题代码**

import java.util.*;
    
    public class Main { 
        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);
        }
    
        private static int getResult(Queue postfix) {
            Stack<Integer> numbers = new Stack<Integer>();
            while(!postfix.isEmpty()){ 
                Object temp = postfix.poll();
                if(temp instanceof Integer)
                    numbers.push((Integer)temp);
                else{
                    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);
        }
    
        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);
                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--;
                    postfixs.offer(number);
                }
                else if(temp == '(')
                    ops.push(temp);
                else if(temp == ')'){
                    char popChar = ops.pop();
                    while(popChar != '('){
                        postfixs.offer(popChar);
                        popChar = ops.pop();
                    }
                }
                else{
                    int rank = getRank(temp);
                    if(ops.isEmpty() || rank > getRank(ops.peek()))
                        ops.push(temp);
                    else {
                        while(!ops.isEmpty() && rank <= getRank(ops.peek()))
                            postfixs.offer(ops.pop());
                        ops.push(temp);
                    }
                }
            }
            while(!ops.isEmpty())
                postfixs.offer(ops.pop());
            return postfixs;
        }
    
        private static int getRank(char c){
            switch (c) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            }
            return -1;
        }
    }