Java: Syntax Parsing(Recursion) Short Solution


  • 0
    X

    The same idea for Basic Calculator I
    https://leetcode.com/discuss/41513/395ms-java-solution-by-syntax-parsing-no-stack

    In this problem, we do not have parentheses but * and /. Since * and / are prior to +/-.

    We should give a new definition for units:

    VALUE: a number

    EXPRESSION: A Sequence of VALUE concat with * and /

    INPUT: A Sequence of EXPRESSION concat with +/-

    OP: operators + - * /

    And we also need to consider whitespaces

    public class Solution {
        int cursor = 0;
        
        //calc a INPUT
        public int calculate(String s) {
            int total = getExp(s);
            char op = '\0';
            
            while(cursor < s.length()){
                op = getOp(s);
                total = (op == '+')? total + getExp(s): total - getExp(s);
            }
            
            return total;
        }
        
        //Only get rid of leading spaces!!! Check getExp()
        public char getOp(String s) {
            while(cursor < s.length() && s.charAt(cursor) == ' ') cursor++;
            
            char op = s.charAt(cursor++);
    
            return op;
        }
        
        //VALUE means a number
        public int getValue(String s) {
            //leading spaces
            while(cursor < s.length() && s.charAt(cursor) == ' ') cursor++;
            
            int num = 0;
            
            while(cursor < s.length() && Character.isDigit(s.charAt(cursor))){
                num *= 10;
                num += s.charAt(cursor++) - '0';
            }
            
            //trailing spaces
            while(cursor < s.length() && s.charAt(cursor) == ' ') cursor++;
            return num;
        }
        
        //EXP means a Value or a Value */ SEQ
        public int getExp(String s) {
            int total = getValue(s);
    
            //check if there is sny * or /
            while(cursor < s.length()){
                char op = getOp(s);
                
                if(op == '*' || op == '/'){
                    total = (op == '*')? total * getValue(s) : total / getValue(s);
                }else{
                    //have read a +/-, cursor should go back 1 step
                    //That is why getOp() should only consider leading spaces
                    cursor--;
                    break;
                }
            }
            
            return total;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.