COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies

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 want you to implement the basic algorithm for evaluating a postfix expressions described on page 373 of your textbook. Your program should allow the user to evaluate multiple expressions. After completing an expression, your program should ask the user if they want to evaluate another expression.

You must include all error-checking described in the algorithm in the book. If an error is detected, stop processing the expression and display an appropriate error message.

To simplify the input, you can assume that all operands are non-negative single-digit integers. You should allow the user to type blanks between all operators and operands. In other words, the user might input "2 3 +" or "23+".

Use the linked-list version of the Stack class from Figure 7.12 of the textbook. DO NOT MODIFY THE Stack CLASS except possibly to set the proper data type in the typedef statement.

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:
2 3 4 + *
The value of the expression is 14

More expressions (Y or N)? Y
Enter postfix expression:
5 2 + 2 /
The value of the expression is 3

More expressions (Y or N)? N

Hints:

• The user should enter an expression on a single line. You can either read the line one character at a time, or you can read the line into a string and then process the string one character at a time.
• The tokens on a line are the operators '+', '-', '*', '/' and the digits '0' - '9'. One way to convert a character that is a digit to an integer is:
  

  char token;
  int value;
  if ( token is an digit )
     value = token - '0';   // note that the character in single quotes is a zero
  

Return to Data Structures homepage 

Return to ACC Homepage

URL: http://www.austincc.edu/comer/cosc2436/
Copyright: 2015 by the Austin Community College
Department of Computer Studies. All rights reserved.
Comments to: Bob Comer
Last updated: September 15, 2015

Austin Community College is an equal opportunity educator and employer.