StackType.cpp

/*Matt Short
CPSC 131
Project 5
Purpose: using our stack template write a program that changes
infix expressions to postfix expressions*/
#include<iostream>
#include<string>
#include "StackType.h"
using namespace std;

string GetInfix(string &infix);//gets infix expression and stores in a string
void PrintExpressions(string infix, string postfix);//prints infix and postfix expressions
int Precedence(char op);//function that checks the precedence of the operators
string Postfix(string infix);//function to convert infix to postfix

int main()
{
    string infix;//string to hold infix
    string postfix;//string to hold postfix
    GetInfix(infix);//gets infix expression
    postfix=Postfix(infix);//prints out postfix expression
    try
    {
        PrintExpressions(infix, postfix);
    }
    catch(FullStack exceptionObject)
    {
        cerr<<"Fullstack exception thrown. Stack is full."<<endl;
        exit(2);
    }
    catch(EmptyStack exceptionObject)
    {
        cerr<<"Emptystack exception thrown. Stack is empty."<<endl;
        exit(2);
    }
    return 0;
}
string GetInfix(string &infix)
{
    cout<<"Please enter an infix expression: ";//prompts user to input an infix expression
    getline(cin, infix);//gets infix expression from keyboard
    return infix;//returns infix string
}
string Postfix(string infix)
{
    StackType<char> stack;//creates a variable stack of type char via StackType
    string postfix;//string to hold postfix expression
    int i=0;//counter variable
    char token;//variable to hold an item from infix
    char popped;//variable that holds the most recently popped operator
    bool done;//bool that is true when it's done
    token = infix[0];//initiates token to the first char of infix
        while(token!='=')//decides where to place char from infix string
        {
                if(token>='0' && token <='9')//if char is a number it gets put directly in postfix string
                    postfix+=token;//places char on postfix
                if(token==')')//checks if char is )
                {
                    popped=stack.Top();//popped=top operator on stack
                    stack.Pop();//pops the top operator from stack
                    while(popped!='(')//if popped isn't ( then
                    {
                        postfix+=popped;//operator added to postfix
                        popped=stack.Top();//popped=top operator on stack
                        stack.Pop();//operator popped from stack
                    }
                }
                if(token=='+' || token=='-' || token=='*' || token=='/' || token=='(' || token=='=')//checks if its an operator
                {
                    if(token!='(')//checks if token isn't (
                    {
                        done=false;//done initiated to false
                        while(!stack.IsEmpty() && !done)//while stack isn't empty and done is true
                            if(Precedence(stack.Top())>=Precedence(token))//compares precedence of top of stack and token
                            {
                                postfix+=stack.Top();//if top of stack is >= token top is
                                stack.Pop();//operator popped
                            }else
                                done=true;//done set to true and jumps out of loop
                    }
                    stack.Push(token);//token is pushed onto postfix
                }


                i++;//i increased by 1
                token=infix[i];//token set to next char in infix


        }
        while(!stack.IsEmpty())//while stack isn't empty
        {
        postfix+=stack.Top();//top is added to postfix
        stack.Pop();//top is popped from stack
        }
    return postfix;//returns the postfix expression
}
int Precedence(char op)
{
    switch(op)//switch statement to determine precedence of operators
    {
    case '/': case '*': return 2;//* and / have the highest precedence
    case '+': case '-': return 1;//+ and - are below * and /
    case '(': return 0;//( has the lowest precedence
    default: return -1;
    }
}
void PrintExpressions(string infix, string postfix)
{
    cout<<endl;
    cout<<"Infix expression: "<<infix<<endl;//prints out the infix expression
    cout<<"Postfix expression: "<<postfix<<endl;//prints out the postfix expression
}