My 13ms solution using 2 queues


  • 0
    S

    Similar as using two stacks, the idea is to maintain two queues for both numbers and operands:

    • if (*) (/) is met, keep pushing the numbers and operands into the queues.
    • if (+) (-) is met, collect numbers/operands from the 2 queues and do the calculation, until the queue is empty.
        int calculate(string s) {
            s.push_back('+'); //append "+" sign to make sure the last loop is run
            int output = 0;
            char prev = '+'; // initial condition
            queue<char> op; // queue that holds the operants
            queue<int> num; // queue that holds the numbers
            int tmp = 0;
            for(int i=0; i<s.size(); i++){
                if(isdigit(s[i])) {
                    tmp = 10*tmp + (s[i]-'0');
                    continue;
                }
                if(!isspace(s[i])){    // skip the space
                    num.push(tmp);
                    if(s[i] == '+' || s[i] == '-'){
                        int tmp1 = num.front();
                        num.pop();
                        while(!op.empty()){
                            tmp1 = (op.front() == '*') ? tmp1*num.front() : tmp1/num.front();
                            num.pop();
                            op.pop();
                        }
                        output = (prev == '+') ? output + tmp1: output - tmp1;
                        prev = s[i];
                    }
                    else{
                        op.push(s[i]);
                    }
                    tmp = 0;
                }
            }
            return output;
      }
    

  • 0
    P

    Can we safely assume that, this algorithm is able to evaluate infix expression with out the need to convert it into a postfix expression under certain conditions?


  • 0
    S

    @panchajanya, I am not sure I understand your question correctly. Could you specify what certain conditions you're referring?
    For an infix expression like A + (B * C), the postfix expression would be A B C * +.
    My solution is close to postfix expression but is slightly different. The main idea is to evaluate (x and /) first, before considering (+ and -). So input of A + (B * C) will become A + (B * C)+ in my implementation. At the first + sign, add A to the output; then at the second + sign (which I intentionally pushed back), B*C will be evaluated, and added to the output.


  • 0
    P

    @swimmorning Never mind, I didn't get my basics right when i first look at your solution. I was under the impression an infix expression must always be converted to either postfix or prefix before evaluating it. Anyways, good solution.


Log in to reply
 

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