Monday, November 30, 2015

LeetCode OJ - Basic Calculator II

Problem: 

Please find the problem here.

Solution:

I could have extended the last solution for Basic Calculator to include the multiplication and division, but turn out the judge have a case that stress memory usage, and top down parser are just not good with respect to memory usage, so I hand written a shift reduce parser instead.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/basic-calculator-ii/

#include "LEET_BASIC_CALCULATOR_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

namespace _LEET_BASIC_CALCULATOR_II
{
    class Solution
    {
    public:
        // Scanner states
        unsigned int position;
        char token;
        string* expression;

        void scan()
        {
            while (true)
            {
                if (position < (*expression).size())
                {
                    token = (*expression)[position++];
                }
                else
                {
                    token = '\0';
                }
                if (token != ' ')
                {
                    break;
                }
            }
        }

        // A hand written shift-reduce parser!
        // I could have adapted the previous top-down parsing solution
        // But there is a test case in the judge to stress memory usage, and a top down parser necessarily use up the space because of the recursion
        // A shift-reduce parser can save space by reducing early and not using the stack space
        int calculate(string s)
        {
            const int PLUS = 0;
            const int MINUS = 1;
            const int MULTIPLY = 2;
            const int DIVIDE = 3;

            stack<int> numStack;
            stack<int> sigStack;

            position = 0;
            expression = &s;

            const int EXPECT_DIGIT = 0;
            const int EXPECT_DIGIT_OR_OPERATOR = 1;
            int state = EXPECT_DIGIT;

            int currentNumber = 0;
            while (true)
            {
                scan();
                if (token >= '0' && token <= '9')
                {
                    state = EXPECT_DIGIT_OR_OPERATOR;
                    currentNumber = currentNumber * 10 + (token - '0');
                }
                else
                {
                    if (EXPECT_DIGIT)
                    {
                        throw 1;
                    }
                    numStack.push(currentNumber);
                    currentNumber = 0;
                    if (token == '*' || token == '/')
                    {
                        while (sigStack.size() > 0)
                        {
                            if (sigStack.top() >= MULTIPLY)
                            {
                                int operand2 = numStack.top(); numStack.pop();
                                int operand1 = numStack.top(); numStack.pop();
                                if (sigStack.top() == MULTIPLY)
                                {
                                    numStack.push(operand1 * operand2);
                                }
                                else if (sigStack.top() == DIVIDE)
                                {
                                    numStack.push(operand1 / operand2);
                                }
                                sigStack.pop();
                            }
                            else
                            {
                                break;
                            }
                        }

                        if (token == '*')
                        {
                            sigStack.push(MULTIPLY);
                        }
                        else if (token == '/')
                        {
                            sigStack.push(DIVIDE);
                        }

                        state = EXPECT_DIGIT;
                    }
                    else if (token == '+' || token == '-' || token == '\0')
                    {
                        while (sigStack.size() > 0)
                        {

                            int operand2 = numStack.top(); numStack.pop();
                            int operand1 = numStack.top(); numStack.pop();
                            if (sigStack.top() == PLUS)
                            {
                                numStack.push(operand1 + operand2);
                            }
                            else if (sigStack.top() == MINUS)
                            {
                                numStack.push(operand1 - operand2);
                            }
                            else if (sigStack.top() == MULTIPLY)
                            {
                                numStack.push(operand1 * operand2);
                            }
                            else if (sigStack.top() == DIVIDE)
                            {
                                numStack.push(operand1 / operand2);
                            }
                            sigStack.pop();
                        }
                        if (token == '+')
                        {
                            sigStack.push(PLUS);
                        }
                        else if (token == '-')
                        {
                            sigStack.push(MINUS);
                        }
                        else if (token == '\0')
                        {
                            return numStack.top();
                        }

                        state = EXPECT_DIGIT;
                    }
                }
            }

            return 0;
        }
    };
};

using namespace _LEET_BASIC_CALCULATOR_II;

int LEET_BASIC_CALCULATOR_II()
{
    Solution solution;
    cout << (solution.calculate("3+2*2") == 7) << endl;
    cout << (solution.calculate(" 3/2 ") == 1) << endl;
    cout << (solution.calculate(" 3+5 / 2 ") == 5) << endl;
    return 0;
}

No comments :

Post a Comment