Leetcode P0227"Basic Calculator II" 题解

博文中会简要介绍Leetcode P0227题目分析及解题思路。

“Basic Calculator II”是比较基础的题目。我们可以采用逆波兰算法对表达式求值。该算法的详解可以参考我的这篇博文：表达式求值“利器”：逆波兰算法详解

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

以下是Java的题解代码实现。

class Solution {
    enum Token {
        NON(-1), ADD(0), SUB(0), MUL(1), DIV(1);
        
        private int order;

        private Token(int _order) {
            this.order = _order;
        }
        
        public boolean compare(Token _token) {
            return (this.order >= _token.order);
        }
    }
    
    class Term {
        boolean isToken;
        Token token;
        int num;
        
        public Term(boolean _isToken, Token _token, int _num) {
            this.isToken = _isToken;
            this.token = _token;
            this.num = _num;
        }
        
        public boolean compare(Term term) {
            return (this.isToken && term.isToken 
                && this.token.compare(term.token));
        }
    }
    
    public int calculate(String s) {
        return this.evaluate(this.generateRPN(s));
    }
    
    private int evaluate(List<Term> rpn) {
        Deque<Integer> stack = new LinkedList<>();
        
        for (Term term: rpn) {
            if (!term.isToken) 
                stack.offerFirst(term.num);
            else {
                switch (term.token) {
                    case ADD:
                        stack.offerFirst(stack.pollFirst()+stack.pollFirst());
                        break;
                    case SUB:
                        stack.offerFirst(-stack.pollFirst()+stack.pollFirst());
                        break;
                    case MUL:
                        stack.offerFirst(stack.pollFirst()*stack.pollFirst());
                        break;
                    case DIV:
                        int divisor = stack.pollFirst(), dividend = stack.pollFirst();
                        stack.offerFirst(dividend/divisor);
                        break;
                    default:
                        break;
                }   
            }
        }
        
        return stack.pollFirst();
    }
    
    private List<Term> generateRPN(String s) {
        List<Term> rpn = new ArrayList<>();
        Deque<Term> stack = new LinkedList<>();
        
        int idx=0;
        while (idx < s.length()) {
            char ch = s.charAt(idx);
            Term term = null;
            
            switch (ch) {
                case ' ':
                    break;
                case '+':
                    term = new Term(true, Token.ADD, 0);
                    break;
                case '-':
                    term = new Term(true, Token.SUB, 0);
                    break;
                case '*':
                    term = new Term(true, Token.MUL, 0);
                    break;
                case '/':
                    term = new Term(true, Token.DIV, 0);
                    break;
                default: {
                    int end = idx;
                    while (end < s.length() && Character.isDigit(s.charAt(end))) {
                        ++end;
                    }
                    
                    int num = Integer.parseInt(s.substring(idx, end));
                    rpn.add(new Term(false, Token.NON, num));
                    idx = end-1;
                    break;
                }
            }
            
            if (term != null) {
                while (!stack.isEmpty() && stack.peekFirst().compare(term)) {
                    rpn.add(stack.pollFirst());
                }
                    
                stack.offerFirst(term);
            }
            
            ++idx;
        }
        
        while (!stack.isEmpty()) {
            rpn.add(stack.pollFirst());
        }
        
        return rpn;
    }
}

聖地亞歌

Leetcode P0227"Basic Calculator II" 题解

Search

Table of Contents