Assignment 04 Solution

The purpose of this assignment is to gain experience with the following new concepts: the RPN or postfix expressions, stack data structure.

Project Description:

Write a program to implement the algorithm for evaluating postfix expressions that involve only single-digit integers and the integer operations +, -, *, and /. To trace the action of postfix evaluation, display each token as it is encountered, and display the action of each stack operation.

Note:
1. Each digit or operator should be separated by a space, and end with :
2. You should apply stack ADT in the program. You can use the Standard Template Library (STL) stack instead of Stack class defined in the text book.

Here is an example how to use the STL stack push/pop/top and empty functions which will be used in this project.
#include <iostream
#include <stack
using namespace std;

int main ()
{
stack<int mystack; // Notice the element type in the stack should be specified in the angle bracket.

for (int i=0; i<5; ++i) mystack.push(i);

cout << "Popping out elements...";
while (!mystack.empty())
{
     cout << " " << mystack.top();
     mystack.pop();
}
cout << endl;

return 0;
}

3. You may need to use function isdigit(int c) in standard header file #include<cctype to check if the token character is digit or not.
4. To convert the single digit char c to the represented integer i, a simple method is to assign i by c -'0' (for example):

char c = '5';   // c is character 5
int i = c -'0'; // i is integer 5

5. Your program should also be able to tell if the input postfix expression is illegal (such as has more operands or operators).
6. Paste your test output as the comments at the end of your source file proj8.cpp.
7. Upload your source file to ANGEL drop-box.

A sample run:

Please enter the RPN expression to be evaluated:

9 2 1 + / 4 * :
Token = 9 Push 9
Token = 2 Push 2
Token = 1 Push 1
Token = + Pop 1 Pop 2 Push 3
Token = / Pop 3 Pop 9 Push 3
Token = 4 Push 4
Token = * Pop 4 Pop 3 Push 12
Token = Pop 12
type 'Y' or 'y' to continue or type any other letter to quit: y
(Note: Each digit or operator should be separated by a space, and end with :)
Please enter the RPN expression to be evaluated:

2 3 4 + *:
Token = 2 Push 2
Token = 3 Push 3
Token = 4 Push 4
Token = + Pop 4 Pop 3 Push 7
Token = * Pop 7 Pop 2 Push 14
Token = Pop 14

type 'Y' or 'y' to continue or type any other letter to quit: q
Press any key to continue

 
Powered by