code:
Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
Terms of Agreement:
By using this code, you agree to the following terms...
1) You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for langauges that allow it) freely and with no charge.
2) You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
3) You may link to this code from another website, but ONLY if it is not wrapped in a frame.
4) You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.
//
#include
#include
// ** charStackClass definition ********
// ************************
const int MAX_STACK = 100; // maximum-size-of-stack;
class charStackClass
{
public:
// constructors and destructor:
charStackClass();// default constructor
// Use compiler-supplied copy constructor and destructor
// stack operations:
bool IsEmpty() const;
// Determines whether a stack is empty.
// Precondition: None.
// Postcondition: Returns true if the stack is empty,
// otherwise returns false.
void Push(char NewItem, bool& Success);
// Adds an item to the top of a stack.
// Precondition: NewItem is the item to be added.
// Postcondition: if insertion was successful, NewItem
// is on the top of the stack and Success is true;
// otherwise Success is false.
void Pop(bool& Success);
// Removes the top of a stack.
// Precondition: None.
// Postcondition: if the stack was not empty, the item
// that was added most recently is removed and Success
// is true. However, if the stack was empty, deletion is
// impossible and Success is false.
void Pop(char& StackTop, bool& Success);
// Retrieves and removes the top of a stack.
// Precondition: None.
// Postcondition: if the stack was not empty, StackTop
// contains the item that was added most recently, the
// item is removed and Success is true. However, if the
// stack was empty, deletion is impossible, StackTop is
// unchanged, and Success is false.
void GetStackTop(char& StackTop, bool& Success) const;
// Retrieves the top of a stack.
// Precondition: None.
// Postcondition: if the stack was not empty, StackTop
// contains the item that was added most recently and
// Success is true. However, if the stack was empty, the
// operation fails, StackTop is unchanged, and Success
// is false. The stack is unchanged.
private:
charItems[MAX_STACK]; // array of stack items
intTop;// index to top of stack
}; // end charStackClass
// *************************************
// ************************
// ** intStackClass definition *********
// ************************
struct stackNode;
typedef stackNode * ptrType; // pointer to node
class intStackClass
{
public:
// constructors and destructor:
intStackClass();// default constructor
intStackClass(const intStackClass& S); // copy constructor
~intStackClass();// destructor
// stack operations:
//(For pre- and post-conditions, see cha
// rStackClass above.)
bool IsEmpty() const;
void Push(int NewItem, bool& Success);
void Pop(bool& Success);
void Pop(int& StackTop, bool& Success);
void GetStackTop(int& StackTop, bool& Success) const;
private:
ptrType TopPtr; // points to top of stack
}; // end intStackClass
// *************************************
// ************************
// ** charStackClass implementation ****
// ************************
charStackClass::charStackClass(): Top(-1)
{
} // end default constructor
bool charStackClass::IsEmpty() const
{
return Top < 0;
} // end IsEmpty
void charStackClass::Push(char NewItem, bool& Success)
{
Success = Top < MAX_STACK - 1;
if (Success) // if stack has room for another item
{
++Top;
Items[Top] = NewItem;
} // end if
} // end Push
void charStackClass::Pop(bool& Success)
{
Success = !IsEmpty();
if (Success)// if stack is not empty,
--Top; // pop top
} // end Pop
void charStackClass::Pop(char& StackTop, bool& Success)
{
Success = !IsEmpty();
if (Success)// if stack is not empty,
{
StackTop = Items[Top]; // retrieve top
--Top; // pop top
}
} // end GetStackTop
void charStackClass::GetStackTop(char& StackTop, bool& Success) const
{
Success = !IsEmpty();
if (Success)// if stack is not empty,
StackTop = Items[Top]; // retrieve top
} // end GetStackTop
// End of charStackClass implementation.
//
// *************************************
// ************************
// ** intStackClass implementation *****
// ************************
struct stackNode
{
int Item;
stackNode * Next;
}; // end struct
intStackClass::intStackClass() : TopPtr(NULL)
{
} // end default constructor
intStackClass::intStackClass(const intStackClass& S)
{
if (S.TopPtr == NULL)
TopPtr = NULL; // original list is empty
else
{
// copy first node
TopPtr = new stackNode;
assert(TopPtr != NULL);
TopPtr->Item = S.TopPtr->Item;
// copy rest of list
ptrType NewPtr = TopPtr;// new list pointer
for (ptrType OrigPtr = S.TopPtr->Next;
OrigPtr != NULL;
OrigPtr = OrigPtr->Next)
{
NewPtr->Next = new stackNode;
assert(NewPtr->Next != NULL);
NewPtr = NewPtr->Next;
NewPtr->Item = OrigPtr->Item;
} // end for
NewPtr->Next = NULL;
} // end if
} // end copy constructor
intStackClass::~intStackClass()
{
bool Success;
// pop until stack is empty (Success is false)
Pop(Success);
while (Success)
Pop(Success);
} // end destructor
bool intStackClass::IsEmpty() const
{
return TopPtr == NULL;
} // end IsEmpty
void intStackClass::Push(int NewItem, bool& Success)
{
// create a new node
ptrType NewPtr = new stackNode;
Success = NewPtr != NULL;
if (Success)
{ // allocation successful
// set data portion of new node
NewPtr->Item = NewItem;
// insert the new node
NewPtr->Next = TopPtr;
TopPtr = NewPtr;
} // end if
} // end Push
void intStackClass::Pop(bool& Success)
{
Success = !IsEmpty();
if (Success)
{ // stack is not empty; delete top
ptrType Temp = TopPtr;
TopPtr = TopPtr->Next;
// return deleted node to system
Temp->Next = NULL; // safeguard
delete Temp;
} // end if
} // end Pop
void intStackClass::Pop(int& StackTop, bool& Success)
{
Success = !IsEmpty();
if (Success)
{ // stack is not empty; delete top
StackTop = TopPtr->Item;
ptrType Temp = TopPtr;
TopPtr = TopPtr->Next;
// return deleted node to system
Temp->Next = NULL; // safeguard
delete Temp;
} // end if
} // end Pop
void intStackClass::GetStackTop(int& StackTop, bool& Success) const
{
Success = !IsEmpty();
if (Success) // if stack is not empty,
StackTop = TopPtr->Item; // retrieve top
} // end GetStackTop
// End of intStackClass implementation.
// *************************************
// ************************
// ** main() ***************************
// ************************
int main()
{
charStackClass O; //stack for operators
intStackClass V; //stack for operands
int operand1, operand2; //variable names used for manipulation
int newOperand, finalAnswer; //variables used to place back into stack and the final answer
bool Success; //true/false variable
char ch, top; //variables used to get equation and top of a stack
char equation[MAX_STACK]; //array used to hold postfix equation
int counter = 0; //used as subscript for array
cout << "Enter an equation or Q to quit: \n";
cin.get(ch);
while (ch !='Q')
{
//This loop takes converts the equation from infix to postfix and places it in an array
//Performs the loop until the newline character is encountered
while (ch != '\n')
{
switch (ch)
{
case '(':
//places '(' into stack
O.Push(ch, Success);
break;
case ')':
//Looks at what is on top
O.GetStackTop(top, Success);
//performs while loop until the left '(' is encountered
while (top != '(')
{
//places operator into array
equation[counter] = top;
//Removes operator from stack
O.Pop(top, Success);
//Look at what is on top
O.GetStackTop(top, Success);
counter++;
}
//pops left '(' and discards
O.Pop (Success);
break;
//Cases for both operators '+' and '-' since both are same precedence
case '+':
case '-':
//Inserts ch into operator stack if empty
if (O.IsEmpty())
{
O.Push(ch, Success);
break;
}
//Looks at what is on top
O.GetStackTop(top, Success);
//Places operators into the array in their postfix order
while (!O.IsEmpty() && top != '(' && top != ')')
{
//places operator into array
equation[counter] = top;
//Removes operator from stack
O.Pop(top, Success);
counter++;
//Looks at what is on top
O.GetStackTop(top, Success);
}
//Inserts ch into operator stack
O.Push(ch, Success);
break;
//Cases for both operators '*' and '/' since both are same precedence
case '*':
case '/':
//Inserts ch into operator stack if empty
if (O.IsEmpty())
{
O.Push(ch, Success);
break;
}
//Looks at what is on top
O.GetStackTop(top, Success);
//Places operators into the array in their postfix order
while(!O.IsEmpty() && (top == '*' || top == '/'))
{
//places operator into array
equation[counter] = top;
//Removes operator from stack
O.Pop(top, Success);
counter++;
//Looks at what is on top
O.GetStackTop(top, Success);
}
//Inserts ch into operator stack
O.Push(ch, Success);
break;
//default case, basically for the characters that are really integers
default:
equation[counter] = ch;
counter++;
break;
}//end switch
//gets another character from equation
cin.get(ch);
}//end while loop
//Places anything left in the operator stack at end of equation in array
while (!O.IsEmpty())
{
//Removes operator from stack
O.Pop(ch, Success);
//places operator into array
equation[counter] = ch;
counter++;
}
//Displays the postfix form of the equation
cout << "The postifix form of this equation is: ";
for (int i = 0; i < counter ; i++)
cout << equation[i] ;
cout << endl;
//Performs the evaluation of the postfix equation
for (int x = 0; x < counter ; x++)
{
switch(equation[x])
{
case '0':
//converts from a character to an integer and puts in integer stack
V.Push(0, Success);
break;
case '1':
//converts from a character to an integer and puts in integer stack
V.Push(1, Success);
break;
case'2':
//converts from a character to an integer and puts in integer stack
V.Push(2, Success);
break;
case '3':
//converts from a character to an integer and puts in integer stack
V.Push(3, Success);
break;
case '4':
//converts from a character to an integer and puts in integer stack
V.Push(4, Success);
break;
case '5':
//converts from a character to an integer and puts in integer stack
V.Push(5, Success);
break;
case '6':
//converts from a character to an integer and puts in integer stack
V.Push(6, Success);
break;
case '7':
//converts from a character to an integer and puts in integer stack
V.Push(7, Success);
break;
case '8':
//converts from a character to an integer and puts in integer stack
V.Push(8, Success);
break;
case '9':
//converts from a character to an integer and puts in integer stack
V.Push(9, Success);
break;
default:
//Retrieves operand1
V.Pop(operand1, Success);
//Retrieves operand2
V.Pop(operand2, Success);
if (equation[x] == '*')
//Multiplies operand2 and operand1
newOperand = operand2 * operand1;
else if (equation[x] == '/')
//Divides operand2 by operand1
newOperand = operand2 / operand1;
else if (equation[x] == '+')
//Add operand2 and operand1
newOperand = operand2 + operand1;
else //equation[x] == '-'
//Subtracts operand1 from operand2
newOperand = operand2 - operand1;
//Inserts newOperand back onto integer stack
V.Push(newOperand, Success);
break;
}
}
//resets the equation array to NULL
for (int r = 0 ; r < counter ; r++)
equation[r] = '\0';
//Retrieves finalAnswer from stack
V.Pop(finalAnswer, Success);
cout << "The answer of this equation is: "<< finalAnswer << endl;
cout << "Enter another equation or Q to quit: \n";
cin.get(ch);
}
return 0;
} // end main()