57 lines
1.6 KiB
C++
57 lines
1.6 KiB
C++
#include <cassert>
|
|
#include <functional>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
class Solution {
|
|
static auto
|
|
get_function(const std::string &op) -> std::function<int(int, int)> {
|
|
if (op == "+") {
|
|
return std::plus<int>{};
|
|
} else if (op == "-") {
|
|
return std::minus<int>{};
|
|
} else if (op == "*") {
|
|
return std::multiplies<int>{};
|
|
} else if (op == "/") {
|
|
return std::divides<int>{};
|
|
}
|
|
|
|
assert(false);
|
|
}
|
|
|
|
public:
|
|
auto evalRPN(const std::vector<std::string> &tokens) -> int {
|
|
std::vector<int> stack;
|
|
|
|
for (const auto &token : tokens) {
|
|
if (token == "+" || token == "-" || token == "*" || token == "/") {
|
|
assert(stack.size() >= 2);
|
|
|
|
int right = stack.back();
|
|
stack.pop_back();
|
|
int left = stack.back();
|
|
stack.pop_back();
|
|
|
|
stack.push_back(get_function(token)(left, right));
|
|
} else {
|
|
stack.push_back(std::stoi(token));
|
|
}
|
|
}
|
|
|
|
return stack.back();
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
Solution s;
|
|
|
|
assert(s.evalRPN(std::vector<std::string>{
|
|
{"2"}, {"1"}, {"+"}, {"3"}, {"*"}}) == 9);
|
|
assert(s.evalRPN(std::vector<std::string>{
|
|
{"4"}, {"13"}, {"5"}, {"/"}, {"+"}}) == 6);
|
|
assert(s.evalRPN(std::vector<std::string>{{"10", "6", "9", "3", "+", "-11",
|
|
"*", "/", "*", "17", "+", "5",
|
|
"+"}}) == 22);
|
|
|
|
return 0;
|
|
}
|