Objective

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.

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  #include  using namespace std; int main () { stack 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 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. Paste your test output as the comments at the end of your source file proj5.cpp.

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

Please do the full program exactly how it asks word for word.