Theory: • Algorithm of stack-based RPN (postfix) expression evaluation: Question
ID: 3621735 • Letter: T
Question
Theory:• Algorithm of stack-based RPN (postfix) expression evaluation:
Question: how do you check for invalid format of expression?
• Algorithm of stack-based PN (prefix) expression evaluation
Question: when to terminate?
• More on wikipedia on RPN/PN expressions:
http://en.wikipedia.org/wiki/Reverse_Polish_notation
http://en.wikipedia.org/wiki/Polish_notation
Check: are top 2 elements of the stack both numbers?
If yes:
pop from stack (number x)
pop from stack (number y)
pop from stack (op)
push the result of (y op x) on stack
go back to Check
If no:
push the next element of expression on stack
go back to Check
scan the expression from left to right
for each element, do the following:
{
if it is a number:
push the number on stack
if it is an operation:
pop from stack number x
pop from stack number y
push the result of (y op x) on stack
}
• Specification:
• Operations: you need to implement addition (+), subtraction (-),
multiplication (*), and division (/) for integer numbers.
• Numbers: single-digit or multiple-digit integer numbers (according to levels of
difficulty) in input expression.
• Input:
?? user will provide a character string of RPN or PN expression, valid or invalid,
with numbers and operations separated by space.
?? “q” to exit the program.
• Output:
?? “invalid expression” if input is not in valid RPN or PN form.
?? identify “RPN” or “PN” according to the input string (for level 1 it’s always RPN).
?? output the result of the expression on the same line.
• Difficulty levels & project group:
Level 1: single-digit RPN expression evaluation
Level 2: single-digit RPN & PN expression evaluation
Level 3: multi-digit RPN & PN expression evaluation
•• Extra credit will be given if the requirement above your required level is achieved.
• Your program should meet the exact specification and input / output format.
• Please make sure your stack can handle no less than 32 elements.
• Submission:
• Submit on blackboard before midnight of Nov 28th (Sunday of week 14):
?? your .s file (well commented).
?? a brief write-up on: 1) what features are implemented; 2) how is work divided if
you have multiple group members.
• Sign up for a 15 min demo / Q&A during the 15th week. (If you finish up early, we can
arrange some time during the 14th week as well.)
?? Sample input / output (red indicating input):
input expression: (q to quit)
- + 200 * 15 2 * 100 + 67 02
PN -900
input expression: (q to quit)
16 3 25 + 40 - *
RPN -192
input expression: (q to quit)
32 5 83 * + 42 * 6 + * 2
invalid format!
input expression: (q to quit)
- 3 2 * 5 22 + 4 / 64 2
invalid format!
for level 2
input expression: (q to quit)
18000 3 5 - /
RPN -9000
input expression: (q to quit)
q
bye!
input expression: (q to quit)
6 3 5 + 4 - *
RPN 24
input expression: (q to quit)
- + 2 * 5 2 * 4 + 6 2
invalid format!
input expression: (q to quit)
6
RPN 6
input expression: (q to quit)
3 5 8 * + 4 * 6 + * 2
invalid format!
input expression: (q to quit)
3 2 2 5 + - +
RPN -2
input expression: (q to quit)
q
bye!
level 3
input expression: (q to quit)
6 3 5 + 4 - *
RPN 24
input expression: (q to quit)
/ 7 2
PN 3
input expression: (q to quit)
- + 2 * 5 2 * 4 + 6 2
PN -20
input expression: (q to quit)
3 5 8 * + 4 * 6 + * 2
invalid format!
input expression: (q to quit)
- 3 2 * 5 2 * 4 + 6 2
invalid format!
input expression: (q to quit)
8 2 4 - /
RPN -4
input expression: (q to quit)
q
bye!
Explanation / Answer
Dear,
Here is the code
Postfix evaluation
#include < iostream >
using std::cout; // program uses cout
using std::cin; // program uses cin
using std::endl; // program uses endl
// File --- StackNode.h
// Template StackNode class definition
#ifndef STACKNODE_H
#define STACKNODE_H
// forward declaration of class Stack required to announce that class
// Stack exists so it can be used in the friend declaration
template< typename NODETYPE > class Stack;
template< typename NODETYPE >
class StackNode
{
friend class Stack< NODETYPE >; // make Stack a friend
public:
StackNode( const NODETYPE & ); // constructor
NODETYPE getData() const; // return data in node
private:
NODETYPE data; // data
StackNode< NODETYPE > *nextPtr; // next node in the data-structure
}; // end class StackNode
// constructor
template < typename NODETYPE >
StackNode< NODETYPE > :: StackNode( const NODETYPE &info )
: data( info ), nextPtr( 0)
{
// empty body
} // end StackNode constructor
// return copy of data in the node
template< typename NODETYPE >
NODETYPE StackNode< NODETYPE > :: getData() const
{
return data;
} // end function getData
#endif
// ----------------------------------------------------------------------------
// File Stack.h
// Template Stack class definition
#ifndef STACK_H
#define STACK_H
// #include "listnode.h"
// need to be included if the above StackNode.h saved separately
template< typename STACKTYPE >
class Stack
{
public:
Stack(); // constructor
~Stack(); // destructor
void push( const STACKTYPE & ); // insertion into stack
bool pop(); // deletion from stack
bool isEmpty() const; // check for empty stack
void printStack() const; // print the contents of stack
const STACKTYPE stackTop() const; // top element of the stack
private:
// pointer to top node of the Stack
StackNode< STACKTYPE > *topPtr;
// utility function to allocate memory to new node
StackNode< STACKTYPE > *getNewNode( const STACKTYPE & );
};
// default constructor
template< typename STACKTYPE >
Stack< STACKTYPE >::Stack()
: topPtr( 0 )
{
// empty body
} // end Stack constructor
// destructor
template< typename STACKTYPE >
Stack< STACKTYPE >::~Stack()
{
cout << endl << endl;
if ( !isEmpty() ) // Stack is not empty
{
do
{
// declare currentPtr
StackNode< STACKTYPE > *currentPtr = topPtr;
topPtr = topPtr->nextPtr; // move onto next node
delete currentPtr; // delete the node
} while (topPtr != 0); // end while
// cout << endl << "Deleted all the nodes and exiting from the program.";
} // end if
} // end destructor
// insert into stack at the top
template< typename STACKTYPE >
void Stack< STACKTYPE >::push( const STACKTYPE &value )
{
// get a new node to insert
StackNode< STACKTYPE > *newPtr = getNewNode( value );
// point new node to top node of the stack
if ( !isEmpty() )
newPtr->nextPtr = topPtr;
// update the top in both the situations - empty as well as non-empty
topPtr = newPtr;
} // end function push
// Delete a node from the stack
template< typename STACKTYPE >
bool Stack< STACKTYPE >::pop()
{
if ( isEmpty() ) // when the stack is empty
return false; // delete unsuccessful
else // when stack is not empty
{
// hold top of the stack with tempPtr to delete
StackNode< STACKTYPE > *tempPtr = topPtr;
// deletion takes place and top will be pointing to 2nd top node
topPtr = topPtr->nextPtr;
delete tempPtr; // delete the node (previous top of the stack)
return true; // delete successful
} // end else
} // end function pop
// is stack empty ?
template< typename STACKTYPE >
bool Stack< STACKTYPE >::isEmpty() const
{
return topPtr == 0;
} // end function isEmpty
// return pointer to newly allocated node
template< typename STACKTYPE >
StackNode< STACKTYPE > *Stack< STACKTYPE >::getNewNode(
const STACKTYPE &value )
{
// create a new node and return the same
return new StackNode< STACKTYPE > ( value );
} // end function GetNewNode
// display contents of the stack
template< typename STACKTYPE >
void Stack< STACKTYPE > :: printStack() const
{
if (isEmpty() ) // when stack is empty
{
cout << endl << "The stack is empty. ";
return;
} // end if
StackNode< STACKTYPE > *currentPtr = topPtr;
cout << endl << endl << "The stack is ";
// loop through the stack
while ( currentPtr != 0 )
{
// print the top node's data
cout << currentPtr->data << " ";
// move onto next node of the stack
currentPtr = currentPtr->nextPtr;
} // end while
} // end function printStack
// returns the data of the top node of the stack
template< typename STACKTYPE >
const STACKTYPE Stack< STACKTYPE >::stackTop() const
{
return topPtr->data ;
} // end function StackTop
#endif
// ------------------------------------------------------------------------------
// a utility function to find a given character is an operator or not
bool isOperator(const char c)
{
// check for the various operators
if ( ( c == '+' ) || ( c == '-' ) || ( c == '*' ) ||
( c == '/' ) || ( c == '^' ) || ( c == '%' ) )
return true; // return true if it is
else
return false; // false if the character is not an operator
} // end function isOperator
// main program to test the functionality of the stacks
// by evaluating postfix arithmetic expression
int main() // function main begins program execution
{
Stack< int > myStack; // A Stack of integers
// character array to store postfix arithmetic expression
char postfix[50];
// declare and initialize to keep track of character array
int postc = 0;
// initialize the array with null characters
for ( int i = 0; i < 50; i++ )
postfix[ i ] = '';
// prompt the user for data and read the data from the user
cout << endl << "A program that evaluates "
<< "a postfix arithmetic expression." << endl;
cout << endl << "Enter your choice of a postfix expression : ";
cin.getline( postfix, 50, ' ' ) ;
do // loop through the postfix array
{
// if the currrent character is a digit
if ( ( postfix[ postc ] > 47 ) && ( postfix[ postc ] < 57 ) )
myStack.push( postfix[ postc ] - 48 );
else
// when the current element in postfix is an operator
if ( isOperator (postfix[ postc ] ) )
{
// pop the two top elements into variables x & y
int x = myStack.stackTop();
myStack.pop();
if(!mystack.isEmpty())
{
int y = myStack.stackTop();
myStack.pop();}
else
{
cout<<"Invalid Format! ";
exit(0);
}
// calculate the " y operator x" and push the result into stack
switch ( static_cast (postfix[ postc ] ) )
{
case '+' : myStack.push( y + x); // operator is +
break;
case '-' : myStack.push( y - x); // operator is -
break;
case '*' : myStack.push( y * x ); // operator is *
break;
case '/' : myStack.push( y / x ); // operator is /
break;
case '%' : myStack.push( y % x ); // operator is %
break;
case '^' : int po = 1; // operator is ^
for ( int i = 1; i < x; i++ )
po *= y;
myStack.push( po );
break;
} // end switch
} // end if
postc++; // move onto the next character of the postfix expression
} while ( postfix[ postc ] != '' ); // end do-while
// print the result value of the postfix expression
cout << endl << "The postfix expression value is " << myStack.stackTop();
system("pause")
return 0; // indicate program executed successfully
} // end of function, main
Hope this will help you
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.