Basic Calculator II Solutions in C++

// Source : https://leetcode.com/problems/basic-calculator-ii/
// Author : Hao Chen
// Date   : 2015-06-24


#include <iostream>
#include <sstream>
#include <string>
#include <stack>
using namespace std;

/* 
 * Acuatlly, everything I've already implemented in "Basic Calculator"(RPN way and Design pattern way).
 * So, here, I just use the quick-dirty way - just like the "two stacks solution" in "Basic Calulator".
 */


//Quick & Dirty Solution
bool isOperator(const char ch) {
    return (ch=='+' || ch=='-' || ch=='*' || ch=='/');
}


int Priority(const char c) {
    if (c == '*' || c == '/') {
        return 2;
    } else if (c== '+' || c == '-') {
        return 1;
    } else {
        return 0;
    }
}

long long calculate_exp(long long x, long long y, char op) {
    switch(op) {
        case '+': return x + y;
        case '-': return x - y;
        case '*': return x * y;
        case '/': return x / y;
    }
    return -1;
}


//Two Stacks solution
int calculate_two_stacks(string& s) {

    s += "+0";
    stack<long long> num_stack; //put the number
    stack<char> op_stack; //put the operations

    #define CALCULATE_IT { \
        long long y = num_stack.top(); num_stack.pop(); \
        long long x = num_stack.top(); num_stack.pop(); \
        char op = op_stack.top(); op_stack.pop(); \
        num_stack.push(calculate_exp(x, y, op));\
    }

    for(int i = 0; i < s.size(); i++){
        char ch = s[i];
        if (isspace(ch)) continue;
        if (isdigit(ch)) {
            string num;
            num += s[i];
            while(isdigit(s[i+1])){
                num += s[i+1];
                i++;
            }
            num_stack.push(stoll(num));
            continue;
        }
        if (isOperator(ch)) {
            while (!op_stack.empty() && Priority(op_stack.top()) >= Priority(ch) ) {
                CALCULATE_IT;
            }

            op_stack.push(ch);
        }

    }

    while(!op_stack.empty()){
        CALCULATE_IT;
    }
    
    return num_stack.top();
}


int calculate(string s) {
    return calculate_two_stacks(s);
}

int main(int argc, char**argv) 
{
    string exp = " 3+5 / 2 ";
    if (argc>1) {
        exp = argv[1];
    }

    cout << "\"" << exp << "\" = " << calculate(exp) << endl;

}

/// Source : https://leetcode.com/problems/basic-calculator-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-09-03

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Two Stacks
/// Shunting-Yard Algorithms: https://en.wikipedia.org/wiki/Shunting-yard_algorithm
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int calculate(string s) {

        vector<int> nums;
        vector<char> ops;
        for(int i = 0; i < s.size() ; ){
            if(isdigit(s[i])){
                int num = s[i] - '0';
                int j;
                for(j = i + 1; j < s.size() && isdigit(s[j]); j ++)
                    num = num * 10 + (s[j] - '0');
                i = j;

                nums.push_back(num);
                if(!ops.empty() && (ops.back() == '*' || ops.back() == '/'))
                    calc(nums, ops);
            }
            else if(s[i] != ' '){
                if((s[i] == '+' || s[i] == '-') && !ops.empty() && (ops.back() == '+' || ops.back() == '-'))
                    calc(nums, ops);
                ops.push_back(s[i++]);
            }
            else
                i ++;
        }
        if(nums.size() != 1){
            assert(nums.size() == 2);
            calc(nums, ops);
        }

        return nums.back();
    }

private:
    void calc(vector<int>& nums, vector<char>& ops){

        assert(nums.size() >= 2);
        int second = nums.back();
        nums.pop_back();
        int first = nums.back();
        nums.pop_back();

        assert(!ops.empty());
        char op = ops.back();
        ops.pop_back();

        switch(op){
            case '+': nums.push_back(first + second); return;
            case '-': nums.push_back(first - second); return;
            case '*': nums.push_back(first * second); return;
            case '/': nums.push_back(first / second); return;
            default: assert(false); return;
        }
    }
};


int main() {

    cout << Solution().calculate("3+2*2") << endl; // 7
    cout << Solution().calculate(" 3/2 ") << endl; // 1
    cout << Solution().calculate(" 3+5 / 2 ") << endl; // 5
    cout << Solution().calculate("42") << endl; // 42
    cout << Solution().calculate("1-1+1") << endl; // 1

    return 0;
}