sundeepblue
4/28/2014 - 3:43 PM

evaluate reverse polish notation. Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /

evaluate reverse polish notation. Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, , /. Each operand may be an integer or another expression. Some examples: ["2", "1", "+", "3", ""] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

evaluate reverse polish notation.cp
content_copyfile_download
bool is_operator(string s) {
    if(s == "+" || s == "-" || s == "*" || s == "/") return true;
    return false;
}

int eval(vector<string> &ex) {
    stack<long long> stk;                           // use long long to handle int overflow
    for(int i=0; i<ex.size(); i++) {
        if(is_operator(ex[i])) {
            long long d1 = stk.top(); stk.pop();
            long long d2 = stk.top(); stk.pop();
            if(ex[i] == "+") stk.push(d2 + d1);
            else if(ex[i] == "-") stk.push(d2 - d1); // d2 goes first
            else if(ex[i] == "*") stk.push(d2 * d1);
            else if(ex[i] == "/") {
                if(d1 != 0) stk.push(d2 / d1);      // handle divide by 0
                else return -1;
            }
        } 
        else { // is number
            long long d = stoi(ex[i]);      // stoi. if using atoi, should be d = atoi(ex[i].c_str());
            stk.push(d);
        }
    }
    return (int)stk.top();
}

int main() {
    vector<string> ex = {"2", "1", "+", "3", "*"};
    cout << eval(ex);
}