Program Description
We are going to implement a program to evaluate infix (operator is between the operands) expressions, to report the value of the expression if it is legal and to report an error if not, and to report the postfix representation of the expression.
Background
This assignment will necessitate learning about two basic ideas in computer science:
1. The notion of lexical analysis and parsing
2. The use of expression trees and grammars to evaluate an arithmetic expression.
Lexical analysis and parsing is the process of pulling apart the individual words in a sentence (lexical analysis) and determining if they form valid sentences (parsing). Typically these tasks are implemented as separate processes. We will consider these problems in class and in lab.
You should remember expression trees from the prerequisite to this class. An expression tree has the operators as inner nodes and the operands as their children. For example, here is an expression tree:
Expression trees like the one above can be built from grammars like this one:
<expr> ::= <term> | <term> + <term> | <term> – <term>
<term> ::= <factor> / <factor> | <factor> * <factor> | <factor>
<factor> ::= (<expr>) | <number> |
<number> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0
Each “major” rule in such a grammar becomes a function in a recursive descent parser. Recursive descent parsers enable the parsing of certain categories of grammars including those associated with programming languages.
The Assignment:
When your program runs, you will open a file and read an infix expression of the type we see in the above example. It will parse the expression and build an expression tree similar to the one above, only reflecting the actual expression in the file. Then, your program will implement a stack of doubles and perform a post-order traversal of the tree. During the traversal, if the node contains a number, the number will be pushed on the stack. If the program encounters an operator, it will pop the operands, perform the operation, and push the result back on the stack. At the end of execution, the result of the computation will be on the stack. Additionally, if you print the post-order traversal results, you will show the postfix representation of the expression which, interestingly, does not require the parentheses to achieve the proper precedence of operators!
Deliverables
You will submit the following for this project:
1. Documentation of your program layout including functions, parameters, return values, etc.
2. A User’s manual for your program
3. Any pseudocode you produced for any of the functions.
3. Your source code in C.
4. Any sample output you generate
Program will be tested with the following:
– 1 expression per file (.txt)
– The expression will be written on one line.
You do not have to ignore spaces, tabs, etc. They might appear in the file, but they can be treated as errors just like other illegal characters such as ‘&’.
So, here we go:
(((5*7)-5+6*8)) // legal
(((5*7)-5+6*8) // illegal, mismatched parens
(((5*7)-5^6*8)) // illegal char ^
7) // illegal, mismatched parens
(7) // legal
7-9 // legal
