[zerojudge]a017. 五則運算

a017. 五則運算

先乘除後加減、括號優先程式是怎麼寫的？！不知道你小時後有沒有想過這種問題，至少我是沒有啦:D

做這題要先了解堆疊，對堆疊(Stack)這種資料結構不熟的話可以看看【Ken將】電腦課小教室 - Class.Null - 堆疊與佇列 ，再來了解運算式的前序、中序、後序表示法資料結構教學 : Infix 轉 Postfix

手稿

程式碼如下：

/*a017. 五則運算
*
* 2020/2/28
*/
import java.util.Scanner;
import java.util.Stack;

public class Pa017{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            System.out.println(evaluate(scanner.nextLine())); 
        }
    }

    public static int evaluate(String s){
        String[] exp = s.split(" ");

        Stack ops = new Stack();
        Stack vals = new Stack();

        for(String token: exp){
            if("(".equals(token)){ 
                ops.push(token);
            }else if(")".equals(token)){ 

                // 不斷計算直到遇到右括號
                while(!"(".equals(ops.peek())){
                    vals.push(calc(vals.pop(), ops.pop(), vals.pop()));
                }

                // 把遇到的右括號pop掉
                ops.pop();

            }else if("+-*/%".contains(token)){

                // 如果ops還有運算子 且 ops最頂層運算子的優先順序 >= token運算子的優先順序
                while(!ops.isEmpty() && priority(ops.peek()) >= priority(token)){
                    vals.push(calc(vals.pop(), ops.pop(), vals.pop()));
                }

                ops.push(token);
            }else{
                vals.push(Integer.parseInt(token));
            }
        } 

        while(!ops.isEmpty()){
            vals.push(calc(vals.pop(), ops.pop(), vals.pop()));
        }

        return vals.pop();
    } 

    public static int priority(String op){
        return "*/%".contains(op) ? 2 : "+-".contains(op) ? 1 : 0;
    }

    // ab位置對調
    public static int calc(int b, String operator, int a){
        switch(operator){
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            case "%": return a % b;
            default:
                    System.out.println("unknown operator");
                    return 0;
        }
    }

}