Write a class ArithmeticExpressionEvaluator that evaluates an infix arithmetic e
ID: 3667685 • Letter: W
Question
Write a class ArithmeticExpressionEvaluator that evaluates an infix arithmetic expression. Do this in two steps. First, convert the infix expression to a postfix expression:create a filter InfixToPostfix that converts an arithmetic expression from infix to postfix. Second, evaluate the postfix expression:write a postfix evaluator EvaluatePostfix that takes a postfix expression, eavluates it and print the value. Your program should print the infix expression, postfix expression and the final result.
Explanation / Answer
Infix to Postfix Algorithm
We need in order to be able to evaluate arbitrary arithmetic expressions is an algorithm to translate infix expression to postfix expressions.
Here is the beginning of an outline of that algorithm. The algorithm uses a queue to store the results and a stack to store operators while the algorithm runs. Each operator has a precedence associated with it, as shown in the table.
operator precedence
+ 1
- 1
* 3
/ 3
^ 6
Here is the outline of the algorithm.
Step 1: Scan the tokens from left to right.
Step 2: If you encounter a number token, move it immediately to the result queue.
Step 3: If you encounter an operator and the operator stack is empty, push the operator on the stack.
Step 4: If you encounter an operator whose precedence is greater than that of the operator at the top of the stack, push the new operator on the stack.
Step 5: If you encounter an operator whose precedence is less than or equal to the precedence of the operator at the top of the stack, pop the stack and move the operator from the stack to the output queue. Repeat this step until either the stack empties or an operator appears at the top of the stack whose precedence is smaller than the precedence of the current operator. Push the new operator on the stack.
Step 6: When you reach the end of the input, move any remaining operators from the stack to the result queue.
Consider as Example
There is one correction we will have to make to rule 5 above. This correction applies to multiple appearances of the same operator. The rule as it is written does the correct thing with the example
2*3*4
The rule effectively treats this expression as if it were written
(2*3)*4
and translates it to
2 3 * 4 *
Program for Infix to Postfix
// PREC_TABLE matches order of Token enumeration
struct Precedence
{
int inputSymbol;
int topOfStack;
} PREC_TABLE [ ] =
{
{ 0, -1 }, { 0, 0 }, // EOL, VALUE
{ 100, 0 }, { 0, 99 }, // OPAREN, CPAREN
{ 6, 5 }, // EXP
{ 3, 4 }, { 3, 4 }, // MULT, DIV
{ 1, 2 }, { 1, 2 } // PLUS, MINUS
};
template <typename NumericType>
class Evaluator
{
public:
Evaluator( const string & s ) : str( s )
{ opStack.push_back( EOL ); }
// The only publicly visible routine
NumericType getValue( ); // Do the evaluation
private:
stack<TokenType> opStack; // Operator stack for conversion
stack<NumericType> postFixStack; // Stack for postfix machine
istringstream str; // String stream
// Internal routines
NumericType getTop( ); // Get top of postfix stack
void binaryOp( TokenType topOp ); // Process an operator
void processToken(const Token<NumericType> &lastToken);
// Handle LastToken
};
// Public routine that performs the evaluation.
// Examines the postfix stack to see if a single result
// is left and if so, returns it; otherwise prints error.
template <class NumericType>
NumericType Evaluator<NumericType>::getValue( )
{
Tokenizer<NumericType> tok( str );
Token<NumericType> lastToken;
do
{
lastToken = tok.getToken( );
processToken( lastToken );
} while( lastToken.getType( ) != EOL );
if( postFixStack.isEmpty( ) )
{
cerr << "Missing operand!" << endl;
return 0;
}
NumericType theResult = postFixStack.top( );
postFixStack.pop( );
if( !postFixStack.isEmpty( ) )
cout << "Warning: missing operators!" << endl;
return theResult;
}
// After token is read, use operator precedence parsing
// algorithm to process it; missing opening parentheses
// are detected here.
template <class NumericType>
void Evaluator<NumericType>::processToken(const Token<NumericType> & lastToken )
{
TokenType topOp;
TokenType lastType = lastToken.getType( );
switch( lastType )
{
case VALUE:
postFixStack.push( lastToken.getValue( ) );
return;
case CPAREN:
while( ( topOp = opStack.top( ) ) != OPAREN && topOp != EOL )
binaryOp( topOp );
if( topOp == OPAREN )
opStack.pop( ); // Get rid of opening parentheseis
else
cout << "Missing open parenthesis" << endl;
break;
default: // General operator case
while( PREC_TABLE[ lastType ].inputSymbol <=
PREC_TABLE[ topOp = opStack.top( ) ].topOfStack )
binaryOp( topOp );
if( lastType != EOL )
opStack.push( lastType );
break;
}
}
// top and pop the postfix machine stack; return the result.
// If the stack is empty, print an error message.
template <class NumericType>
NumericType Evaluator<NumericType>::getTop( )
{
if( postFixStack.isEmpty( ) )
{
cout << "Missing operand" << endl;
return 0;
}
NumericType tmp = postFixStack.top( );
postFixStack.pop( );
return tmp;
}
// Process an operator by taking two items off the postfix
// stack, applying the operator, and pushing the result.
// Print error if missing closing parenthesis or division by 0.
template <class NumericType>
void Evaluator<NumericType>::binaryOp( TokenType topOp )
{
if( topOp == OPAREN )
{
cout << "Unbalanced parentheses" << endl;
opStack.pop( );
return;
}
NumericType rhs = getTop( );
NumericType lhs = getTop( );
if( topOp == EXP )
postFixStack.push( pow( lhs, rhs ) );
else if( topOp == PLUS )
postFixStack.push( lhs + rhs );
else if( topOp == MINUS )
postFixStack.push( lhs - rhs );
else if( topOp == MULT )
postFixStack.push( lhs * rhs );
else if( topOp == DIV )
if( rhs != 0 )
postFixStack.push( lhs / rhs );
else
{
cout << "Division by zero" << endl;
postFixStack.push( lhs );
}
opStack.pop( );
}
// A simple main to exercise Evaluator class.
int main( )
{
string str;
while( getline( cin, str ) )
{
Evaluator<int> e( str );
cout << e.getValue( ) << endl;
}
return 0;
}
Postfix Expression
Arithmetic expression in infix form have operators written between the numbers they operate on. An alternative form is postfix form, which writes the operator after the two things it operates on. For example, the postfix equivalent of
1 + 2
Is 1 2 + and the postfix equivalent of
1 + 2 * 3 is 1 2 3 * +
There is a very simple algorithm for evaluating postfix expressions.
Step 1: Scan the expression from left to right.
Step 2: Push any numbers you encounter on a value stack.
Step 3: Any time you encounter an operator, pop the top two numbers off the value stack, apply the operation to them, and push the result back on the stack.
Step 4: The number that appears at the top of the stack at the end of the scan is the result of the calculation.
Program for Postfix Expression
#include <stack>
#include <iostream>
#include "token.h"
using namespace std;
typedef Token<int> tokenType;
int pow(int x,int y)
{
int result = 1;
while(y > 0)
{
result *= x;
y--;
}
return result;
}
int main()
{
stack<tokenType> s;
Tokenizer<int> t(cin);
tokenType curToken = t.getToken();
while(curToken.getType() != EOL)
{
// Process the current token
switch(curToken.getType())
{
case EOL:
break;
case VALUE:
s.push(curToken);
break;
case OPAREN:
case CPAREN:
break;
case EXP:
{
tokenType op1 = s.top();
s.pop();
tokenType op2 = s.top();
s.pop();
int result = pow(op2.getValue(),op1.getValue());
s.push(Token<int>(VALUE,result));
break;
}
case MULT:
{
tokenType op1 = s.top();
s.pop();
tokenType op2 = s.top();
s.pop();
int result = op2.getValue()*op1.getValue();
s.push(Token<int>(VALUE,result));
break;
}
case DIV:
{
tokenType op1 = s.top();
s.pop();
tokenType op2 = s.top();
s.pop();
int result = op2.getValue()/op1.getValue();
s.push(Token<int>(VALUE,result));
break;
}
case PLUS:
{
tokenType op1 = s.top();
s.pop();
tokenType op2 = s.top();
s.pop();
int result = op2.getValue()+op1.getValue();
s.push(Token<int>(VALUE,result));
break;
}
case MINUS:
{
tokenType op1 = s.top();
s.pop();
tokenType op2 = s.top();
s.pop();
int result = op2.getValue()-op1.getValue();
s.push(Token<int>(VALUE,result));
break;
}
}
curToken = t.getToken();
}
tokenType last = s.top();
cout << "Result: " << last.getValue() << endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.