Introduction
CPSC 131
Project 4 Requirements
Representing and Evaluating Arithmetic Expressions
We typically write arithmetic expressions with the operator placed in between its two operands.
For example, “2 + 3”; here, + is the operator and its two operands are 2 and 3. This notation is called Infix notation. The main disadvantage of infix notation is that the order of operations sometimes needs to be made clear with matching sets of parentheses. For example, “2 + 3 x 5” is different from “(2 + 3) x 5.” Therefore, computers represent arithmetic expressions using different notations where the order of operations is unambiguous without using additional symbols like parentheses.
In this project, you will implement two such representations, the Reverse Polish Notation and
Expression Trees and convert between representations.
Expression Trees
( Refer to Example 7.9 in page 285 of the textbook.) An arithmetic expression can be represented with a binary tree. For example, an expression of 3+5 can be represented by a binary tree shown below.
Similarly, an expression of (3+5)*4 can be represented by
A binary tree of an arithmetic expression can be constructed if we know its Reverse Polish notation (RPN).
Reverse Polish Notation (RPN)
RPN (also called postfix notation) is a mathematical notation in which every operator follows all of its operands. For example, the expression 3+5 can be rewritten as “3 5 +” and (3+5)*4 can be
rewritten as “3 5 + 4 *”. Visit https://en.wikipedia.org/wiki/Reverse_Polish_notation for more
information about Reverse Polish notation.
Converting between representations
Converting from Expression Tree to RPN
Note that the postOrder traversal of an arithmetic binary tree gives the exact same expression as its Reverse Polish notation.
Converting from RPN to Expression Tree
Here, we use an example of “3 5 + 4*” to explain how to use RPN notation to construct a binary tree. First, create a stack that will contain nodes of a binary tree we are trying to build. Then, we parse the notation from left to right by steps:
‘3’ is an operand.
Create a node with it and push the node to stack (stack contains one node).
‘5’ is an operand.
Create a node with it and push the node to stack (stack contains two nodes).
‘+’ is an operator.
Create a node with it, connect its left child and right child pointer with two nodes pop out of
stack, and then push this node to stack (stack contains one node).
For every operator you parse in the expression, two operand nodes need to pop out of stack
since RPN requires that every operator follows all of its two operands.
’4’ is an operand
Create a node with it and push the node to stack (stack contains two nodes).
‘*’, is an operator.
Create a node with it, connect its left child and right child pointer with two nodes pop out of
stack, and then push this node to stack (stack contains one node)
Continue if there are more characters in expression.
The whole process can be simplified as a sequence of operations shown below.
push(3)
push(5)
push((pop()+pop())
push(4)
push (pop() *pop())
At the end, there will be only one node in stack that is the root of this arithmetic binary tree.
Converting from Expression Tree to Infix Notation
An inorder traversal of an arithmetic binary tree where an open parentheses is output before
calling a left child and a close parentheses is output after returning from a right child gives a fully parenthesized infix expression. For example, the expression tree shown earlier results in “((3 + 5) *
4)”. Refer to Algorithm printExpression in page 303 of the textbook.
Converting from Infix Notation to RPN
Description of algorithm from 3.9.2. General Infix-to-Postfix Conversion, Problem Solving with
Algorithms and Data Structures using Python ;
http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressio
ns.html
Assume the infix expression is a string of tokens delimited by spaces. The operator tokens are *, /, +,
and -, along with the left and right parentheses, ( and ). The operand tokens are integers. The
following steps will produce a string of tokens in postfix order.
1. Create an empty stack called opstack for keeping operators. Create an empty list for output.
2. Convert the input infix string to a list of tokens – operators, operands, or parentheses.
3. Scan the token list from left to right.
If the token is an operand, add it to the end of the output list.
If the token is a left parenthesis, push it on the opstack.
If the token is a right parenthesis, pop the opstack until the corresponding left
parenthesis is removed. Add each operator to the end of the output list.
If the token is an operator, *, /, +, or -, push it on the opstack. However, first remove
any operators already on the opstack that have higher or equal precedence and add
them to the output list.
4. When the input expression has been completely processed, check the opstack. Any
operators still on the stack can be removed and added to the end of the output list.
Evaluating expressions
Evaluating an expression is computing its final answer. It is much easier to evaluate expressions
represented in RPN or as Expression Trees than in infix notation.
Evaluating expression trees
The postorder traversal of an expression tree can be used to solve the evaluation problem. Refer to Evaluating an Arithmetic Expression in page 298 of the textbook for the algorithm.
Evaluating RPN expressions
A single stack is sufficient to evaluate an RPN expression.
Description of algorithm from 3.9.2. General Infix-to-Postfix Conversion, Problem Solving with
Algorithms and Data Structures using Python ;
http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressio
ns.html
Assume the postfix expression is a string of tokens delimited by spaces. The operators are *, /, +,
and -. The operands are assumed to be integers. The output will be an integer result (assuming
divison returns only the integer quotient).
1. Create an empty stack called operandStack.
2. Scan the token list from left to right.
If the token is an operand, convert it from a string to an integer and push the value
onto the operandStack.
If the token is an operator, *, /, +, or -, it will need two operands. Pop the
operandStack twice. The first pop is the second operand and the second pop is the
first operand. Perform the arithmetic operation. Push the result back on the
operandStack.
3. When the input expression has been completely processed, the result is on the stack. Pop
the operandStack and return the value.
Objective
You are to write a C++ program that will ask the user to enter an arithmetic expression in either infix or RPN. Your program should then return the expression in other notations (infix, RPN, and expression trees) and evaluate the expression into an integer. To do these, you will have to implement the algorithms
described above.
You are given the declarations of functions which will be called from main() to convert and evaluate expressions. Your are also given a class ArithNode which is to be used for nodes of a binary expression tree.
You are to write the definitions of only the functions, adding other functions as needed. Your code is tested in the provided main.cpp .
Simplifying assumptions
There are only four binary operators: + – * /. The division operator returns the integer quotient.
Operands are positive integers.
There will be a space between every token – operators, operands, and parentheses.
There is no need for error checking (i.e., operators and operands will be as described above;
parentheses will be matched).
The infix and RPN expressions will be input/output as strings. Expression trees will be
represented as a pointer to the root node (* ArithNode ). The leaves of the expression trees
(operands) should have null left and right child pointers (not empty “external” nodes).
You are given the code to “print” an expression tree in main.cpp. You just need to construct the tree.
● There are multiple ways to implement some of the functions. For example, to evaluate an infix
expression, you can convert to RPN and evaluate the RPN expression, or convert to an expression tree and evaluate the tree. You only need to implement one method (your choice).
● Note that since each function is a stand-alone function, they are not made part of a class.
● You will need to use other data structures, especially a stack. It is recommended that you use the C++ Standard Library containers (std::stack).
Source Code Files
The starter C++ code has multiple files:
● ExpressionConverter.h : This contains the declarations of the functions to be
implemented. This also contains the class ArithNode. This file is already complete and you
should not change this code.
● ExpressionConverter.cpp : This is to be completed with definitions of the functions
which will be called from main(). You can add other functions as needed.
● main.cpp : Code that brings everything together into one application. The main function also
tests the output of your functions. This is already complete and you should not change this code.
● A README.md file. You must edit this file to include the name and CSUF email address of each student in your group as in other projects.
Obtaining and submitting code
We will again be using GitHub Classroom to distribute starter code. The assignment link is:
https://classroom.github.com/g/8r6pk2xh
When you choose a team name make sure it begins with your section number (1, 2, 3, 4,
5, 6, or 8). Example: 2-myteamname