online advertising

Monday, October 31, 2016

LeetCode OJ - Evaluate Reverse Polish Notation

Problem:

Please find the problem here.

Solution: 

A stack machine work perfectly for this case! Be careful with subtraction/division case. Remember the stack pops the second argument first!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/evaluate-reverse-polish-notation/

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

using namespace std;

namespace _LEET_EVALUATE_REVERSE_POLISH_NOTATION
{
    class Solution {
    public:
        int evalRPN(vector<string>& tokens) {
            stack<int> args;
            for (int i = 0; i < tokens.size(); i++)
            {
                if (tokens[i] == "+")
                {
                    int a = args.top(); args.pop();
                    int b = args.top(); args.pop();
                    args.push(a + b);
                }
                else if (tokens[i] == "-")
                {
                    int a = args.top(); args.pop();
                    int b = args.top(); args.pop();
                    args.push(b - a);
                }
                else if (tokens[i] == "*")
                {
                    int a = args.top(); args.pop();
                    int b = args.top(); args.pop();
                    args.push(a * b);
                }
                else if (tokens[i] == "/")
                {
                    int a = args.top(); args.pop();
                    int b = args.top(); args.pop();
                    args.push(b / a);
                }
                else
                {
                    args.push(stoi(tokens[i]));
                }
            }

            return args.top();
        }
    };
};

using namespace _LEET_EVALUATE_REVERSE_POLISH_NOTATION;

int LEET_EVALUATE_REVERSE_POLISH_NOTATION()
{
    Solution solution;
    string input_array[5] = { "4", "13","5","/","+" };
    vector<string> input(input_array, input_array + 5);
    cout << solution.evalRPN(input) << endl;
    return 0;
}

No comments :

Post a Comment