TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
postfix_evaluation.cpp
Go to the documentation of this file.
1
14#include <algorithm> // for all_of
15#include <cassert> // for assert
16#include <iostream> // for io operations
17#include <stack> // for std::stack
18#include <string> // for stof
19#include <vector> // for std::vector
20
25namespace others {
30namespace postfix_expression {
31
37bool is_number(const std::string &s) {
38 return !s.empty() && std::all_of(s.begin(), s.end(), ::isdigit);
39}
40
49void evaluate(float a, float b, const std::string &operation,
50 std::stack<float> &stack) {
51 float c = 0;
52 const char *op = operation.c_str();
53 switch (*op) {
54 case '+':
55 c = a + b; // Addition of numbers
56 stack.push(c);
57 break;
58
59 case '-':
60 c = a - b; // Subtraction of numbers
61 stack.push(c);
62 break;
63
64 case '*':
65 c = a * b; // Multiplication of numbers
66 stack.push(c);
67 break;
68
69 case '/':
70 c = a / b; // Division of numbers
71 stack.push(c);
72 break;
73
74 default:
75 std::cout << "Operator not defined\n";
76 break;
77 }
78}
79
80namespace {
81float remove_from_stack(std::stack<float> &stack) {
82 if (stack.empty()) {
83 throw std::invalid_argument("Not enough operands");
84 }
85 const auto res = stack.top();
86 stack.pop();
87 return res;
88}
89} // namespace
90
97float postfix_evaluation(const std::vector<std::string> &input) {
98 std::stack<float> stack;
99
100 for (const auto &scan : input) {
101 if (is_number(scan)) {
102 stack.push(std::stof(scan));
103
104 } else {
105 const auto op2 = remove_from_stack(stack);
106 const auto op1 = remove_from_stack(stack);
107
108 evaluate(op1, op2, scan, stack);
109 }
110 }
111
112 const auto res = remove_from_stack(stack);
113 if (!stack.empty()) {
114 throw std::invalid_argument("Too many operands");
115 }
116 return res;
117}
118} // namespace postfix_expression
119} // namespace others
120
126static void test_function_1() {
127 std::vector<std::string> input = {"2", "3", "1", "*", "+", "9", "-"};
128
130
131 assert(answer == -4);
132}
133
139static void test_function_2() {
140 std::vector<std::string> input = {"100", "200", "+", "2", "/",
141 "5", "*", "7", "+"};
143
144 assert(answer == 757);
145}
146
147static void test_function_3() {
148 std::vector<std::string> input = {
149 "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1",
150 "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1",
151 "+", "+", "+", "+", "+", "+", "+", "+", "+", "+", "+",
152 "+", "+", "+", "+", "+", "+", "+", "+", "+", "+"};
154
155 assert(answer == 22);
156}
157
158static void test_single_input() {
159 std::vector<std::string> input = {"1"};
161
162 assert(answer == 1);
163}
164
165static void test_not_enough_operands() {
166 std::vector<std::string> input = {"+"};
167 bool throws = false;
168 try {
170 } catch (std::invalid_argument &) {
171 throws = true;
172 }
173 assert(throws);
174}
175
176static void test_not_enough_operands_empty_input() {
177 std::vector<std::string> input = {};
178 bool throws = false;
179 try {
181 } catch (std::invalid_argument &) {
182 throws = true;
183 }
184 assert(throws);
185}
186
187static void test_too_many_operands() {
188 std::vector<std::string> input = {"1", "2"};
189 bool throws = false;
190 try {
192 } catch (std::invalid_argument &) {
193 throws = true;
194 }
195 assert(throws);
196}
197
202int main() {
205 test_function_3();
206 test_single_input();
207 test_not_enough_operands();
208 test_not_enough_operands_empty_input();
209 test_too_many_operands();
210
211 std::cout << "\nTest implementations passed!\n";
212
213 return 0;
214}
for std::invalid_argument
Definition stack.hpp:19
void pop()
Definition stack.hpp:62
void push(const value_type &item)
Definition stack.hpp:47
value_type top() const
Definition stack.hpp:56
for vector
Functions for Postfix Expression algorithm.
void evaluate(float a, float b, const std::string &operation, std::stack< float > &stack)
Evaluate answer using given last two operands from and operation.
bool is_number(const std::string &s)
Checks if scanned string is a number.
float postfix_evaluation(const std::vector< std::string > &input)
Postfix Evaluation algorithm to compute the value from given input array.
static void test_function_2()
Test function 2 with input array {'100', '200', '+', '2', '/', '5', '*', '7', '+'}...
static void test_function_1()
Test function 1 with input array {'2', '3', '1', '*', '+', '9', '-'}.
int main()
Main function.