COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies
Program 4 - Evaluating Postfix Expressions
Be sure to read through Chapter 7 of the textbook before starting this assignment.
Do Programming Problem 12 at the end of Chapter 7 in the Nyhoff textbook (page 387-388). You do not have to print the trace - just print the value of the expression.
I just want you to implement the basic algorithm described on page 373 of your textbook. You must include all error-checking described in the algorithm in the book. If an error is detected, print an appropriate error message and ignore the rest of the expression.
You can assume that all operands are non-negative single-digit integers. To simplify the input, you can also assume that all operators and operands are blank-separated.
Use the linked-list version of the Stack class from Figure 7.12 of the textbook. Source code for examples in the textbook can be found at the author's web site:
http://cs.calvin.edu/books/c++/ds/2e/
The sourse code for Figure 7.12 is here:
http://cs.calvin.edu/activities/books/c++/ds/2e/SourcePrograms/Chap07/Figure7.12/
Your driver program should have a loop that allows the user to evaluate multiple expressions.
For example, your output might look like:
Enter postfix expression with tokens separated by blanks: 2 3 4 + * The value of the expression is 14 More expressions (Y or N)? Y Enter postfix expression with tokens separated by blanks: 5 2 + 2 / The value of the expression is 3 More expressions (Y or N)? N
Hints:
char token; int value; if ( token is an operand ) value = token - 48; // the ascii code for '0' is 48, '1' is 49, etc.One way to convert a string containing a single digit to an integer is:
string token; int value; if ( token is an operand ) value = token[0] - 48; // the ascii code for '0' is 48, '1' is 49, etc.
Return to Data Structures homepage
Return to ACC Homepage