[LeetCode] 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.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Note: What can be done through stl stack, can also be done through stl vector.

class Solution {

public:
    int calculate(string s) {
        vector<int> numbers;
        vector<char> operators;
        int i = 0;
        while(i<s.length())
        {
            char e = s[i++];
            if(e == ' ') continue;
            
            if(isdigit(e))
            {
                int j = i;
                while(j < s.length() && isdigit(s[j]) ) j++;
                int num = stoi(s.substr(i-1, j-i+1));
                i = j;
                if(!operators.empty() && 
                    (operators.back() == '*' 
                    || operators.back() == '/')
                  )
                {
                    char op = operators.back();
                    operators.pop_back();
                    if(op == '*') numbers.back() *= num;
                    else numbers.back() /= num;
                }
                else numbers.push_back(num);
                
            }
            else operators.push_back(e);
        }
        
        if(numbers.empty()) return 0;
        int a = numbers[0];
        int opIndex = 0;
        for(int i = 1;i<numbers.size();i++)
        {
            char op = operators[opIndex++];
            if(op == '+') a += numbers[i];
            else a -= numbers[i];
        }
        return a;
    }
};

[LeetCode] Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Note: when the element to push is equal to the top of min stack, it should be push.

class MinStack {
    stack<int> elements;
    stack<int> minElements;
public:
    void push(int x) {
        elements.push(x);
        if(minElements.empty() || 
                x <= minElements.top()) {
            minElements.push(x);
        }
    }

    void pop() {
        if(elements.empty()) return;
        
        int t = elements.top();
        if(t == minElements.top()){
            minElements.pop();
        }
        elements.pop();
    }

    int top() {
        return elements.top();
    }

    int getMin() {
        return minElements.top();
    }
};

[LintCode] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Example

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

class Solution {
public:
    /**
     * @param tokens The Reverse Polish Notation
     * @return the value
     */
    int evalRPN(vector<string>& tokens) {
        // Write your code here
        int len = tokens.size();
        if(len == 0) return 0;
        stack<int> s;
        int start = 0;
        while(start<len){
            
            if(tokens[start].length() == 1 
                && !isalnum(tokens[start][0])) {
                
                int a = s.top();
                s.pop();
                int b = s.top();
                s.pop();
                if(tokens[start][0] == '+') s.push(a+b);
                else if(tokens[start][0] == '-') s.push(b-a);
                else if(tokens[start][0] == '*') s.push(a*b);
                else if(tokens[start][0] == '/') s.push(b/a);
            }
            else {
                s.push(stoi(tokens[start]));
            }
            start++;
        }
        
        return s.top();
    }
};

[LeetCode] Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

class Solution
{
public:
     int largestRectangleArea(vector<int> &height) 
     {
        height.push_back(0);
        int len = height.size();
        stack<int> s;
        s.push(-1);
        int maxArea = 0;
        int i = 0;
        while(i < len)
        {
            if(height[i]>= height[s.top()]){
                s.push(i);
                i++;
            }
            else
            {
                int tp = s.top();
                s.pop();
                maxArea = max(maxArea, height[tp]*(i-1-s.top()));
            }
        }
        return maxArea;
    }
};

[LeetCode] Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0, last = -1;
        int len = s.length();
        
        stack<int> stack;
        for(int i=0;i<len;i++)
        {
            if(s[i] == '(')
            {
                stack.push(i);
            }
            else
            {
                if(stack.empty())
                {
                    last = i;
                    continue;
                }
                stack.pop();
                if(stack.empty())
                {
                    //last is the first ')' without matching
                    maxLen = max(maxLen, i-last);
                }
                else
                {
                    //the top of stack is the first '(' without match
                    maxLen = max(maxLen, i-stack.top());
                }
            }
        }
        return maxLen;
    }
};

[LeetCode] Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

class Solution {
public:
    bool isValid(string s) {
        stack<char> pStack;
        unordered_map<char,char> map;
        map['}'] = '{';
        map[']'] = '[';
        map[')'] = '(';
        for(int i=0;i<s.length();i++)
        {
            if(s[i] == '(' || s[i] == '{' || s[i] == '[')
            {
                pStack.push(s[i]);
            }
            else if (pStack.empty())
            {
                return false;
            }
            else if(map[s[i]] == pStack.top())
            {
                pStack.pop();
            }
            else
            {
                return false;
            }
        }
        return pStack.empty();
    }
};