题解 | #表达式求值#

编译原理写法

• E -> E (+|-) T
• T -> T * F
• F -> (E) | n
• 空间复杂度为O（n）

public class Solution {

    enum Type{
        LB,RB,ADD,SUB,MUL,END,NUM
    }

    String s;

    Type tokenId;

    char c;

    int num = 0;

    int idx;

    public int solve (String s) {
        // write code here
        this.s = s;
        getToken();
        return E();
    }

    private int E(){
        int n = T();
        while(tokenId == Type.ADD || tokenId == Type.SUB){
            if(tokenId == Type.ADD) {
                match(Type.ADD);
                n += T();
            }
            else {
                match(Type.SUB);
                n -= T();
            }
        }
        return n;
    }

    private int T(){
        int n = F();
        while(tokenId == Type.MUL){
            match(Type.MUL);
            n *= F();
        }
        return n;
    }

    private int F(){
        int n = 0;
        if(tokenId == Type.LB){
            match(Type.LB);
            n = E();
            match(Type.RB);
        }
        else {
            n = num;
            match(Type.NUM);
        }
        return n;
    }

    private void match(Type id){
        if(id != tokenId){
            System.out.println("..");
        }
        getToken();
    }

    private void getToken(){
        if(idx == s.length()){
            tokenId = Type.END;
            return;
        }
        c = s.charAt(idx++);
        if(c == '(') tokenId = Type.LB;
        else if(c == ')') tokenId = Type.RB;
        else if(c == '+') tokenId = Type.ADD;
        else if(c == '-') tokenId = Type.SUB;
        else if(c == '*') tokenId = Type.MUL;
        else{
            num = c - '0';
            tokenId = Type.NUM;
            while(idx < s.length()){
                char nextC = s.charAt(idx);
                if(nextC >= '0' && nextC <= '9'){
                    num = num * 10 + nextC - '0';
                    idx++;
                }
                else
                    break;
            }
        }
    }
}