TITLE

EVALUATING PREFIX EXPRESSIONS USING A POINTER-BASED STACK

INTRODUCTION

The conventional notation in which we are accustomed to write arithmetic expressions is called infix notation, since in it, operators are written between their operands: X + Y. In prefix notation, the operator precedes the operands: + X Y. Prefix epressions can be evaluated with a stack-based algorithm. The stack in this case holds both operands (values) and operators (characters).

DESCRIPTION

Design, implement, document, and test a program that reads prefix expressions from a file, one expression per line. The program echoes the expressions, evaluates them using the stack-based algorithm described in class, and reports their values.

INPUT

The program reads the name of a file, then from the file reads syntactically correct postfix expressions involving single-digit integers and the binary arithmetic operators +, -, *, and /.

OUTPUT

The program prompts for the input file name and prints to the terminal each expression in the file and its value.

ERRORS

The program can assume that its input is as described; it need not detect any errors.

EXAMPLE

If a data file prefix.dat is this:

 * + 3 4 3 * 5 / 4 + 3 - 2 1 * 9 * 2 - 5 + 2 4 

then a run of the program might look like this:

 Enter input file name: postfix.dat Expression: * + 3 4 3 Value = 21. Expression: * 5 / 4 + 3 - 2 1 Value = 5. EXPRESSION: * 9 * 2 - 5 + 2 4 Value = -18. 

Of course, you must show more than three tests, and they must differ from these. Choose your own examples.

OTHER REQUIREMENTS

Implement the stack abstract data type in a class. Use a linked (pointer-based) stack implementation. That is, a stack is represented by a simple singly-linked list, and the first Node in the list is the top of the stack.

HINTS

The stack in this case must hold both operands (values) and operators (characters). Consider the following structure for the Nodes in the linked list that represents a stack.

 struct Node { int value; char optr; bool is_value; Node *next; }; 

This structure requires push() to accept three parameters and pop() to return three values (through reference parameters).

Another option eliminates the char field. When a character is assigned to an integer field, the character's ASCII value is written. The Boolean field then indicates how the value field should be interpreted. In this case, both push() and pop() have two explicit parameters.

Include in the stack class an operation that examines the top three elements of a stack to determine if it is time to carry out an operation.

Operands are only single digits; this greatly simplifies input, and allows us to concentrate on the evaluation algorithm and its use of the stack. Read input characters, and extract digits' integer values: ch-'0'.

Consider a function in the client program called, say, apply(op, opnd1, opnd2) that returns the value that results when the operator op is applied to the two operands that are the function's second and third parameters.

BONUS

For up to ten bonus points, extend the program to handle multi-digit integers while still reading the input one character at a time. (Hint: Horner's Rule.)