TITLE

EVALUATING POSTFIX EXPRESSIONS USING A 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 postfix notation, the operator follows the operands: X Y +. Postfix epressions can be easily evaluated with a stack-based algorithm.

DESCRIPTION

Design, implement, document, and test a program that reads postfix 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.

OTHER REQUIREMENTS

Implement a stack abstract data type in a class. Use a sequential (array-based) stack implementation.

HINTS

The program will use a stack of integers (for operands) and will therefore #include a class that implements a stack of integers.

Note that operands will be 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(optr, opnd1, opnd2) that returns the value that results when the operator optr 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.)

This is what I have for the project, but how can I extend the progrma to handle multi-digit integers while still reading the input one character at a time?

#include #include #include #include

using namespace std;

int eval(int a, int b, char symbol) { switch (symbol) { case '+': return b + a; case '-': return b - a; case '*': return b * a; case '/': return b / a; default : return 0; } }

int postFix(string postfix) { stack s; int i = 0; char ch; int val; while (i < postfix.length()) { ch = postfix[i]; if(ch != ' ') if (isdigit(ch)) { s.push(ch-'0'); } else { int op1 = s.top(); s.pop(); int op2 = s.top(); s.pop(); val = eval(op1, op2, ch); s.push(val); } i++; } return val; }

int main() { ifstream file ("postfix.dat"); string temp; int count = 0; while (getline(file, temp)) { cout << "Expression: " << temp << endl; cout << "Value = " << postFix(temp) << "." << endl << endl; } return 0; }