C++ Programming: EVALUATING GENERAL INFIX EXPRESSIONS

INTRODUCTION

The conventional notation in which we usually write arithmetic expressions is called infix notation; in it, operators are written between their operands: X + Y. Such expressions can be ambiguous; do we add or multiply first in the expression 5 + 3 * 2? Parentheses and rules of precedence and association clarify such ambiguities: multiplication and division take precedence over addition and subtraction, and operators associate from left to right.

This project implements and exercises a stack-based algorithm that evaluates infix expressions according to the conventional rules of precedence and association.

DESCRIPTION

Design, implement, document, and test a program that reads infix 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 general infix expressions involving single-digit integers and 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 infix.dat is this:

 5 + 7 * (9 - 6) + 3 8 + 4 / 2 (8 + 4) / 2 (6 + (7 - 3)) * ((9 / 3) + 2) * 4 

then a run of the program might look like this:

 Enter input file name: infix.dat Expression: 5 + 7 * ( 9 - 6 ) + 3 Value = 29. Expression: 8 + 4 / 2 Value = 10. Expression: ( 8 + 4 ) / 2 Value = 6. Expression: ( 6 + ( 7 - 3 ) ) * ( ( 9 / 3 ) + 2 ) * 4 Value = 200. 

OTHER REQUIREMENTS

Implement a stack abstract data type in a class. Use a linked (pointer-based) stack implementation.

HINTS

The program will use two stacks, one of integers (for operands) and one of characters (for operators), so it will #include two stack classes that differ only in the types of object in their stacks.

Operands will be single digits; this greatly simplifies input and allows us to concentrate on the evaluation algorithm and its interaction with the stacks. (If you wrote a multi-digit integer function for the previous project, you can use it here if you like.)

Consider a function 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.