Principle: LIFO (First In First Out)
Header: <stack>
Methods: push(), pop(), top()
Examples: Check balance for Parenthesis (), Braces {}, Brackets []
You've learned how to use stacks in C++ for various applications. Now, put your knowledge to the test by evaluating an expression in Reverse Polish Notation (also known as postfix notation), where operands precede the operator. In other words, the operator comes after the two numbers on which it is supposed to operate.
Your task is to write a function that processes such an expression and returns the result. Remember, in a Reverse Polish Notation expression like "1 2 + 4 -", the operation is performed from left to right. This means you first add 1 and 2, and then subtract 4 from the result, getting -1 as a final result.
Assume the expression only includes + and - operators. Hint: you can use std::stoi to convert a (numeric) string into an integer value.#include "solution.hpp"
#include <climits>
int evaluate_reverse_polish_notation(const std::string &expression) {
// TODO: processe a RPN expression and return the result
std::stack<int> value;
for (const auto& ch : expression) {
if (ch != ' ') {
if (ch == '+') {
if (value.size() < 2) {
return INT_MIN;
}
int back = value.top();
value.pop();
int front = value.top();
value.pop();
value.push(back+front);
} else if (ch == '-') {
if (value.size() < 2) {
return INT_MIN;
}
int back = value.top();
value.pop();
int front = value.top();
value.pop();
value.push(front - back);
} else {
value.push(ch - '0');
}
}
}
if (value.size() == 1) {
return value.top();
} else {
return INT_MIN;
}
}
int main() {
// The expression "1 2 + 4 -" is "(1 + 2) - 4"
std::cout << evaluate_reverse_polish_notation("1 2 + 4 -") << std::endl; // Expected output: -1
return 0;
}'테크 > CodeSignal-C++' 카테고리의 다른 글
| 6. Browsing system for Deque (0) | 2024.11.30 |
|---|---|
| 5. Map using custom object key (0) | 2024.11.29 |
| 4. Multimap to Map (0) | 2024.11.28 |
| 3. Map & Multimap (0) | 2024.11.26 |
| 2. Queue and Deque (0) | 2024.11.23 |
