Share my C++ solution with demonstration, easy to understand


  • 0
    V

    (1+(4+5+2)-3)+(6+8)


    ( 1+(4+5+2)-3)+(6+8)
    stack_op:(
    stack_num:


    (1+(4+5+2)-3)+(6+8)
    stack_op:(
    stack_num:1


    (1 + (4+5+2)-3)+(6+8)
    stack_op:(+
    stack_num:1


    (1+ ( 4+5+2)-3)+(6+8)
    stack_op:(+(
    stack_num:1


    (1+(4+5+2)-3)+(6+8)
    stack_op:(+(
    stack_num:1 4


    (1+(4 + 5+2)-3)+(6+8)
    stack_op:(+(+
    stack_num:1 4


    (1+(4+5+2)-3)+(6+8)
    stack_op:(+(+
    stack_num:1 4 5
    stack_op:(+(
    stack_num:1 9


    (1+(4+5 + 2)-3)+(6+8)
    stack_op:(+(+
    stack_num:1 9


    (1+(4+5+2)-3)+(6+8)
    stack_op:(+(+
    stack_num:1 9 2
    stack_op:(+(
    stack_num:1 11


    (1+(4+5+2 ) -3)+(6+8)
    stack_op:(+
    stack_num:1 11
    stack_op:(
    stack_num:12


    (1+(4+5+2) - 3)+(6+8)
    stack_op:(-
    stack_num:12


    (1+(4+5+2)-3)+(6+8)
    stack_op:(-
    stack_num:12 3
    stack_op:(
    stack_num:9


    (1+(4+5+2)-3 ) +(6+8)
    stack_op:
    stack_num:9


    (1+(4+5+2)-3)+(6+8)
    stack_op:+
    stack_num:9


    (1+(4+5+2)-3)+ ( 6+8)
    stack_op:+(
    stack_num:9 6


    (1+(4+5+2)-3)+(6+8)
    stack_op:+(
    stack_num:9 6


    (1+(4+5+2)-3)+(6 + 8 )
    stack_op:+(+
    stack_num:9 6


    (1+(4+5+2)-3)+(6+8)
    stack_op:+(+
    stack_num:9 6 8
    stack_op:+(
    stack_num:9 14


    (1+(4+5+2)-3)+(6+8 )
    stack_op:+
    stack_num:9 14
    stack_op:
    stack_num:23

    class Solution {
    public:
        int calculate(string s) {
            int len = s.length();
            stack<char> stack_op;
            stack<int> stack_num;
            int ret = 0;
            int i = 0;
            
            while (i < len)
            {
                if (s[i] == ' ')
                    i++;
                else if (isdigit(s[i]))
                {
                    int num = s[i++] - '0';
                    
                    while (i < len && isdigit(s[i]))
                        num = num * 10 + s[i++] - '0';
                        
                    stack_num.push(num);
                    
                    while (!stack_op.empty() && stack_op.top() != '(')
                    {
                        char ch = stack_op.top();
                        stack_op.pop();
                        
                        int num2 = stack_num.top();
                        stack_num.pop();
                        int num1 = stack_num.top();
                        stack_num.pop();
                        
                        if (ch == '+')
                            stack_num.push(num1 + num2);
                        else
                            stack_num.push(num1 - num2);
                    }
                }
                else if (s[i] == '(' || s[i] == '+' || s[i] == '-')
                    stack_op.push(s[i++]);
                else if (s[i] == ')')
                {
                    while (stack_op.top() != '(')
                    {
                        char ch = stack_op.top();
                        stack_op.pop();
                        
                        int num2 = stack_num.top();
                        stack_num.pop();
                        int num1 = stack_num.top();
                        stack_num.pop();
                        
                        if (ch == '+')
                            stack_num.push(num1 + num2);
                        else
                            stack_num.push(num1 - num2);
                    }
                    
                    i++;
                    stack_op.pop();// pop the '('
                    
                    while (!stack_op.empty() && stack_op.top() != '(')
                    {
                        char ch = stack_op.top();
                        stack_op.pop();
                        
                        int num2 = stack_num.top();
                        stack_num.pop();
                        int num1 = stack_num.top();
                        stack_num.pop();
                        
                        if (ch == '+')
                            stack_num.push(num1 + num2);
                        else
                            stack_num.push(num1 - num2);
                    }
                }
            }
            
            if (!stack_num.empty())
                ret = stack_num.top();
            
            return ret;
        }
    };
    

Log in to reply
 

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