C++ stack solution.


  • 19
    C
    int calculate(string s) {
        stack<int> myStack;
        char sign = '+';
        int res = 0, tmp = 0;
        for (unsigned int i = 0; i < s.size(); i++) {
            if (isdigit(s[i]))
                tmp = 10*tmp + s[i]-'0';
            if (!isdigit(s[i]) && !isspace(s[i]) || i == s.size()-1) {
                if (sign == '-')
                    myStack.push(-tmp);
                else if (sign == '+')
                    myStack.push(tmp);
                else {
                    int num;
                    if (sign == '*' )
                        num = myStack.top()*tmp;
                    else
                        num = myStack.top()/tmp;
                    myStack.pop();
                    myStack.push(num);
                } 
                sign = s[i];
                tmp = 0;
            }
        }
        while (!myStack.empty()) {
            res += myStack.top();
            myStack.pop();
        }
        return res;
    }

  • 0

  • -6

  • 1
    G

    test cases in leetcode is too weak,considering the situation "-5-1 * -3", " * " followed by "-",then your solution will not get the correct answer!


  • 0
    A

    The numbers are non-negative as mentioned in the problem.


  • -1
    W

    The same situation happened when test case is set as "-5-1 ** 3". It has nothing to do with the non-negative problem. The problem for this solution is that it cannot handle the situation with continuous more than one operators. Although this might not be a correct expression, this is the situation that we should be able to handle. Isn't it?


  • 0
    A

    @wen_chieh The problem clearly states You may assume that the given expression is always valid. This solution solves the specified problem, no need to make it more complicated than it is.


  • 0
    T

    Great solution! I modified your code to take advantage of istringstream, which leads to a more straightforward and concise answer.
    In fact, it can be further improved by removing the stack, just use two integer to save the current total value and the last operand. This is exactly what Stefan did.

     int calculate(string s) {
            stack<int> stk;
            int a;
            istringstream iss(s);
            char op = '+';
            while (iss >> a){
                if (op == '+' || op == '-'){
                    stk.push(op == '+' ? a : -a);
                } 
                else{
                    int last = stk.top();
                    stk.pop();
                    if (op == '*') last *= a;
                    else last /= a;
                    stk.push(last);
                }
                iss >> op;
            }
            int sum = 0;
            while(!stk.empty()){
                sum += stk.top();
                stk.pop();
            }
            return sum;
        }
    

  • 0
    C

    @guoqingpei Question states there are no negative numbers.


Log in to reply
 

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