Stacks are used by compilers to help in the process of evaluating expressions and generating machine language code. In this and the next exercise, we investigate how compilers evaluate arith- metic expressions consisting only of constants, operators and parentheses.
Humans generally write expressions like 3 + 4 and 7 / 9 in which the operator (+ or / here) is written between its operands—this is called infix notation. Computers “prefer” postfix notation in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as 3 4 + and 7 9 /, respectively.
To evaluate a complex infix expression, a compiler would first convert the expression to postfix notation and evaluate the postfix version of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack object in support of its
operation, and in each algorithm the stack is used for a different purpose.
In this exercise, you will write a C++ version of the infix-to-postfix conversion algorithm. In the next exercise, you will write a C++ version of the postfix expression evaluation algorithm. Later in the chapter, you will discover that code you write in this exercise can help you implement a com-
plete working compiler.
Write a program that converts an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers such as
(6 + 2) * 5 - 8 / 4
to a postfix expression. The postfix version of the preceding infix expression is
6 2 + 5 * 8 4 / -
The program should read the expression into character array infix and use modified versions of the stack functions implemented in this chapter to help create the postfix expression in character array postfix. The algorithm for creating a postfix expression is as follows:
1) Push a left parenthesis '(' onto the stack.
2) Append a right parenthesis ')' to the end of infix.
3) While the stack is not empty, read infix from left to right and do the following:
If the current character in infix is a digit, copy it to the next element of postfix.
If the current character in infix is a left parenthesis, push it onto the stack.
If the current character in infix is an operator,
Pop operators (if there are any) at the top of the stack while they have equal or
higher precedence than the current operator, and insert the popped
operators in postfix.
Push the current character in infix onto the stack.
If the current character in infix is a right parenthesis
Pop operators from the top of the stack and insert them in postfix until a left
parenthesis is at the top of the stack.
Pop (and discard) the left parenthesis from the stack.
The following arithmetic operations are allowed in an expression:
+ addition
- subtraction
* multiplication
/ division
^ exponentiation
% modulus
[Note: We assume left-to-right associativity for all operators for the purpose of this exercise.] The stack should be maintained with stack nodes, each containing a data member and a pointer to the next stack node.
Some of the functional capabilities you may want to provide are:
a) function convertToPostfix that converts the infix expression to postfix notation
b) function isOperator that determines whether c is an operator
c) function precedence that determines whether the precedence of operator1 is less than, equal to or greater than the precedence of operator2 (the function returns –1, 0 and 1, respectively)
d) function push that pushes a value onto the stack
e) function pop that pops a value off the stack
f) function stackTop that returns the top value of the stack without popping the stack
g) function isEmpty that determines if the stack is empty
h) function printStack that prints the stack
// Definition of class template StackNode.
#ifndef STACKNODE_H
#define STACKNODE_H
template< typename T > class Stack; // forward declaration
template < typename T >
class StackNode
{
friend class Stack< T >;
public:
StackNode( const T & = 0, StackNode * = 0 );
T getData() const;
// set point to next stack node
void setNextPtr( StackNode *nPtr )
{
nextPtr = nPtr;
} // end function setNextPtr
// get point to next stack node
StackNode *getNextPtr() const
{
return nextPtr;
} // end function getNextPtr
private:
T data;
StackNode *nextPtr;
}; // end class StackNode
// member-function definitions for class StackNode
// constructor
template < typename T >
StackNode< T >::StackNode( const T &d, StackNode< T > *ptr )
{
data = d;
nextPtr = ptr;
} // end constructor
// get data
template < typename T >
T StackNode< T >::getData() const
{
return data;
} // end function getData
#endif
// Definition of class template Stack.
// NOTE: This Stack class is a standalone Stack class template.
#ifndef STACK_H
#define STACK_H
#include
#include
#include "StackNode.h"
using namespace std;
template < typename T >
class Stack
{
public:
Stack(); // default constructor
~Stack(); // destructor
void push( T & ); // insert item in stack
T pop(); // remove item from stack
bool isEmpty() const; // is the stack empty?
T stackTop() const; // check the top value
void print() const; // output the stack
// return pointer to first stack node
StackNode< T > *getTopPtr() const
{
return topPtr;
} // end function getTopPtr
private:
StackNode< T > *topPtr; // pointer to first StackNode
}; // end class template Stack
// member-function definitions for class template Stack
template < typename T >
Stack< T >::Stack()
{
topPtr = 0;
} // end constructor
template < typename T >
Stack< T >::~Stack()
{
StackNode< T > *tempPtr, *currentPtr = topPtr;
while ( currentPtr != 0 )
{
tempPtr = currentPtr;
currentPtr = currentPtr->getNextPtr();
delete tempPtr;
} // end while
} // end destructor
// push node
template < typename T >
void Stack< T >::push( T &d )
{
StackNode< T > *newPtr = new StackNode< T >( d, topPtr );
topPtr = newPtr;
} // end function push
// pop node
template < typename T >
T Stack< T >::pop()
{
StackNode< T > *tempPtr = topPtr;
topPtr = topPtr->nextPtr;
T poppedValue = tempPtr->data;
delete tempPtr;
return poppedValue;
} // end function pop
// is the stack empty?
template < typename T >
bool Stack< T >::isEmpty() const
{
return topPtr == 0;
} // end function isEmpty
// get the top node
template < typename T >
T Stack< T >::stackTop() const
{
return !isEmpty() ? getTopPtr()->getData() : static_cast< T >( 0 );
} // end function stackTop
// display the stack
template < typename T >
void Stack< T >::print() const
{
StackNode< T > *currentPtr = topPtr;
if ( isEmpty() ) // Stack is empty
cout << "Stack is empty\n";
else // Stack is not empty
{
cout << "The stack is:\n";
while ( currentPtr != 0 )
{
cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
} // end while
cout << '\n';
} // end else
} // end function print
#endif
// Infix to postfix conversion
#include
#include
using namespace std;
#include "Stack.h"
// function prototype
void convertToPostfix( char * const, char * const );
bool isOperator( char );
bool precedence( char, char );
int main()
{
const int MAXSIZE = 100;
char c;
char inFix[ MAXSIZE ];
char postFix[ MAXSIZE ];
int pos = 0;
cout << "Enter the infix expression.\n";
// get input
while ( ( c = static_cast< char >( cin.get() ) ) != '\n' )
if ( c != ' ' )
inFix[ pos++ ] = c;
inFix[ pos ] = '\0';
cout << "The original infix expression is:\n" << inFix << '\n';
// change from infix notation into postfix notation
convertToPostfix( inFix, postFix );
cout << "The expression in postfix notation is:\n" << postFix << endl;
return 0; // indicates successful termination
} // end main
// take out the infix and change it into postfix
void convertToPostfix( char * const infix, char * const postfix )
{
Stack< char > charStack;
int infixCount;
int postfixCount;
bool higher;
char popValue;
char leftParen = '(';
// push a left paren onto the stack and add a right paren to infix
charStack.push( leftParen );
charStack.print();
strcat( infix, ")" );
// convert the infix expression to postfix
for ( infixCount = 0, postfixCount = 0; charStack.stackTop();
infixCount++ )
{
if ( isdigit( infix[ infixCount ] ) )
postfix[ postfixCount++ ] = infix[ infixCount ];
else if ( infix[ infixCount ] == '(' )
{
charStack.push( leftParen );
charStack.print();
} // end else if
else if ( isOperator( infix[ infixCount ] ) )
{
higher = true; // used to store value of precedence test
while ( higher )
{
if ( isOperator( charStack.stackTop() ) )
{
if ( precedence( charStack.stackTop(),
infix[ infixCount ] ) )
{
postfix[ postfixCount++ ] = charStack.pop();
charStack.print();
} // end if
else
higher = false;
} // end if
else
higher = false;
} // end while
charStack.push( infix[ infixCount ] );
charStack.print();
} // end else if
else if ( infix[ infixCount ] == ')' )
{
while ( ( popValue = charStack.pop() ) != '(' )
{
charStack.print();
postfix[ postfixCount++ ] = popValue;
} // end while
charStack.print();
} // end else if
} // end for
postfix[ postfixCount ] = '\0';
} // end function convertToPostfix
// check if c is an operator
bool isOperator( char c )
{
if ( c == '+' || c == '-' || c == '*' || c == '/' || c == '^' )
return true;
else
return false;
} // end function isOperator
// ensure proper order of operations
bool precedence( char operator1, char operator2 )
{
if ( operator1 == '^' )
return true;
else if ( operator2 == '^' )
return false;
else if ( operator1 == '*' || operator1 == '/' )
return true;
else if ( operator1 == '+' || operator1 == '-' )
{
if ( operator2 == '*' || operator2 == '/' )
return false;
else
return true;
} // end else if
return false;
} // end function precedence
Enter the infix expression.
(6 + 2) * 5 - 8 / 4
The original infix expression is:
(6+2)*5-8/4
The stack is:
(
The stack is:
( (
The stack is:
+ ( (
The stack is:
( (
The stack is:
(
The stack is:
* (
The stack is:
(
The stack is:
- (
The stack is:
/ - (
The stack is:
- (
The stack is:
(
Stack is empty
The expression in postfix notation is:
62+5*84/-
You might also like to view...
Answer the following statements true (T) or false (F)
1. It is possible for a structure to contain as a member a pointer to its own structure type. 2. The statement Rectangle * boxer; defines a variable boxer to be a pointer pointing to a type Rectangle. 3. An array name is a pointer constant because the address it represents cannot be changed during run-time. 4. A temporary value in a program can be referred to by at most one l value reference.
The ReadLine method requires you to provide the file's name.
Answer the following statement true (T) or false (F)
To uniquely identify a UNIX file, combine one or more directory names and a file name to form a __________.
a. file extension b. path name c. working directory d. subdirectory
Jane, a security administrator, wants to prevent users in sales from accessing their servers after 6:00 p.m., and prevent them from accessing accounting's network at all times. Which of the following should Jane implement to accomplish these goals?
A. Separation of duties B. Time of day restrictions C. Access control lists D. Mandatory access control E. Single sign-on