USING C++ Polish notation/expression is also known as ‘prefix notation’ where th
ID: 3700378 • Letter: U
Question
USING C++
Polish notation/expression is also known as ‘prefix notation’ where the numbers are preceded by its operator (placed in the front). In RPN, the operator comes after the operands instead of the normal format in which the operator is between the operations (this is called infix notation).
Starting with an empty stack, a RPN calculator can be implemented with the following rules:
If a number is input, push it o the stack.
If “+” is input then pop value1, pop value2, then push value2-value1 on the stack.
If “-“ is input, then pop the last two operands off the stack, multiply them, and push the result on the stack.
If “/” is input, then pop value1, pop value2, then push value2/value1on the stack.
If “q” is input, then stop inputting values, print out the top of the stack, and exit the program.
Modify the Stack class given in the class to store integers instead of characters. Use the modified stack to implement a RPN calculator. Output an appropriate error message if there are not two operands on the stack when given an operator.
Here is a sample input and output that is equivalent to ( (10 – ( 2 + 3 ) * 2 ) ) / 5:
10
2
3
+
-
2
*
5
/
q
The top of the stack is: 2
Explanation / Answer
C++ code for stated problem: with output
#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>
using namespace std;
int pop(vector<int>& stk);
int main() {
vector<int> opndStack;
string token;
while (cin >> token) {
if (isdigit(token[0])) {
opndStack.push_back(atoi(token.c_str()));
} else {
int left, right;
switch (token[0]) {
case '+': opndStack.push_back(pop(opndStack) + pop(opndStack));
break;
case '-': right = pop(opndStack);
left = pop(opndStack);
opndStack.push_back(left - right);
break;
case '*': opndStack.push_back(pop(opndStack) * pop(opndStack));
break;
case '/': right = pop(opndStack);
left = pop(opndStack);
opndStack.push_back(left / right);
break;
default: throw domain_error("Undefined operator");
}
cout << "Result: " << opndStack.back() << endl;
}
}
return 0;
}
int pop(vector<int>& stk) {
if (stk.empty()) {
throw underflow_error("Stack underflow.");
}
int result = stk.back();
stk.pop_back();
return result;
}
output:
10 2 3 + - 2 * 5 /
Result: 5
Result: 5
Result: 10
Result: 2 which is top of stack
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.