遞歸——四則運算表達式求值

問題

輸入為四則運算表達式，僅由整數、+、－、、/ 、(、)組成，沒有空格，要求求其值。假設運算符結果都是整數。"/"結果也是整數。

輸入：(2+3)(5+7)+9/3

輸出： 63

分析

好難，還是有點困惑，邏輯懂了，但是怎麼想出來的呢？

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        String x = reader.nextLine();
        char[] a = x.toCharArray();
        Stack ori = new Stack();
        for (int i = a.length - 1; i >= 0; i--) {
            ori.push(a[i]);//原棧
        }
        System.out.println(expression_value(ori));
    }

    public static int expression_value(Stack expression) {//求一個表達式的值
        int result=term_value(expression);
        boolean more=true;
        while (more){
            if(!expression.empty()){
                char op=(char)expression.peek();//看一個字元,不取走
                if (op=='+'||op=='-'){
                    expression.pop();
                    int value=term_value(expression);
                    if (op=='+'){
                        result+=value;
                    }else{
                        result-=value;
                    }
                }else {
                    more=false;
                }
            }else {
                break;
            }
        }
        return result;
    }

    public static int term_value(Stack term) {//求一個項的值
        int result=factor_value(term);
        while (true){
            if(!term.empty()){
                char op=(char)term.peek();//看一個字元,不取走
                if (op=='*'||op=='/'){
                    term.pop();
                    int value=factor_value(term);
                    if (op=='*'){
                        result*=value;
                    }else{
                        result/=value;
                    }
                }else {
                    break;
                }
            }else{
                break;
            }
        }
        return result;
    }
    public static int factor_value(Stack factor) {//求一個因子的值
        int result=0;
        char op=(char)factor.peek();//看一個字元,不取走
        if (op=='('){
            factor.pop();
            result=expression_value(factor);
            factor.pop();
        }else {
            while (Character.isDigit(op)){
                result=10*result+op-'0';
                factor.pop();
                if(!factor.empty()){
                    op=(char)factor.peek();
                }
                else {
                    break;
                }
            }
        }
        return result;
    }
}

           

排疑

1 不懂為什麼要term_value,直接加減乘除放一起啊

經調試發現，如果隻要expression_value和factor_value,那麼最後計算結果為

(2+3)*(5+7)先加9，最後得到的結果/3，而原本應該先9/3，再二者相加

是以加減和乘除必須分開，若無括号，乘除優先級比加減高，要先判斷是否有乘除操作