227. Basic Calculator II (Medium)

https://leetcode.com/problems/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.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.

Solutions

class Solution {

    public int calculate(String s) {
        // format the s and split it to valid pieces.

        // remove blank space
        s = s.replace(" ", "").trim();

        List<String> elements = new ArrayList<>();

        // Firstly, split all the elements.

        while (!s.isEmpty()) {
            boolean findOp = false;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '+' || c == '-' || c == '*' || c == '/') {
                    findOp = true;

                    // add integer value
                    elements.add(s.substring(0, i));

                    // add operand
                    elements.add(s.substring(i, i + 1));

                    // trunk the string
                    s = s.substring(i + 1);

                    break;
                }
            }

            if (!findOp) {
                elements.add(s);

                break;
            }
        }

        // adopt a stack to keep elements for backtracking purpose
        Stack<String> stack = new Stack<>();

        // Secondly, process operands of * and /

        for (int i = 0; i < elements.size(); i++) {

            // right value of an expression if current element is a operand
            String e1 = elements.get(i);

            // pop out if meets higher priority operand
            if (!stack.isEmpty() && (stack.peek().equals("*") || stack.peek().equals("/"))) {
                // pop out the operand
                String op = stack.pop();

                // pop out left value for multiplication
                String e2 = stack.pop();

                // push back the result
                if (op.equals("*")) {
                    stack.push("" + (Integer.valueOf(e1) * Integer.valueOf(e2)));
                } else {
                    stack.push("" + (Integer.valueOf(e2) / Integer.valueOf(e1)));
                }

                continue;
            }

            // Push in low priority elements
            stack.add(e1);
        }

        int ans = 0;

        // Finally, process operands of + and -

        // Interpret the +,- expression from tail to head. But it is recommend to make it from head to tail.
        String preE = stack.pop();
        while (!stack.isEmpty()) {

            String e = stack.pop();
            if (e.equals("+")) {
                ans += Integer.valueOf(preE);

                continue;
            }

            if (e.equals("-")) {
                ans -= Integer.valueOf(preE);

                continue;
            }

            preE = e;
        }

        // Do not forget the first left element
        ans = ans + Integer.valueOf(preE);

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-21 16:03:31

results matching ""

    No results matching ""