14ms Java with stacks


  • 0
    G

    This is basically a refactoring of Java -- Easy Version to Understand, but using a private inner stack class.

    public class Solution {
        private LinkedStack<Integer> st;
        
        private class LinkedStack<Item> {
            private Node first = null;
            
            /**
             * Places input _item_ on the top of the stack.
             * @param item 
             */
            public void push(Item item) {
                Node old = first;
                first = new Node();
                first.item = item;
                first.next = old;
            }
            
            /**
             * Removes the item from the top of the stack and returns it.
             * @return 
             */
            public Item pop() {
                Item item = first.item;
                first = first.next;
                return item;
            }
            
            /**
             * Returns true if the stack has no items in it, false otherwise.
             * @return 
             */
            public boolean isEmpty() {
                return (first == null);
            }
            
            /**
             * The Node is the class from which a linked list is built.
             * The stack here relies on a linked list implementation.
             */
            private class Node {
                Item item;
                Node next;
            }
        }
        
        public int calculate(String s) {
            st = new LinkedStack<>();
            int sign = 1;
            int rst = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c >= '0' && c <= '9') {
                    int num = c - '0';
                    while (i + 1 < s.length() &&
                            (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9')) {
                        num = num * 10 + s.charAt(i + 1) - '0';
                        i++;
                    }
                    rst += num * sign;
                }
                else {
                    switch (c) {
                        case '+':
                            sign = 1;
                            break;
                        case '-':
                            sign = -1;
                            break;
                        case '(':
                            st.push(rst);
                            st.push(sign);
                            rst = 0;
                            sign = 1;
                            break;
                        case ')':
                            rst = st.pop() * rst + st.pop();
                            break;
                    }
                }
            }
            return rst;
        }
    }
    

Log in to reply
 

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