Infix to Postfix

[marsh]

Hey, i was assigned this as homework. I am following a sheet of paper that is basically telling me what should be done at each step of the conversion. I have filled in the code but i am getting crashes at various steps of the program.

The stack code i made at the start worked fine but now it assigns random values and goes NULL for no reason. I have changed a ton of the code to get past certain errors and now its just starting to fall apart.

Any ideas on how i could get this working? I am considering just scrapping the entire thing and starting fresh. Am

#include "stdafx.h"
#include <stdlib.h>

// TODO: get rid of break statement
// TODO: Append to end function

struct stack
{
    char data;
    stack* belowData;
};

// Just to keep code cleaner
stack* push(char data, stack* currentStack);
stack* pop(stack* currentStack);
int isOperator(char data);
int precedence(char operator1, char operator2);
void convertToPostfix(char infix[], char postfix[] );
char stackTop(stack* currentStack);
bool isEmpty(stack* currentStack);
void printStack(stack* currentStack);


int _tmain(int argc, _TCHAR* argv[])
{
	stack* pCurrentNode = (stack*)malloc(sizeof(stack));
    pCurrentNode->data = NULL;

    char infix[50];
	char postfix[50];
	int infixCharCount = 0;

	int postCount = 0;

	printf("Enter a postfix operation. Ex: 1 + 2 / 1\n\n");
	scanf("%s",&infix);


	// Push a left parenthesis onto the stack
	pCurrentNode = push('(' ,pCurrentNode);

	// Append a right parentheseis to the end of infix
	for(int a = 0; a < 50; a++)
	{
		if(infix[a] == NULL)
		{
			// Get size of array since where already here
			infixCharCount = a;


			infix[a] = ')';
			infix[a + 1] = NULL;
			break;
		}
	}

	// While the stack is not empty.
	while(isEmpty(pCurrentNode) == false)
	{
		//printStack(pCurrentNode);
		for(int a = 0; a < infixCharCount; a++)
		{
			if(isEmpty(pCurrentNode) == true)
			{
				break;
			}

			// Is a digit
			if( isOperator(infix[a]) == 0)
			{
				// Append a right parentheseis to the end of postfix
				for(int a = 0; a < infixCharCount; a++)
				{
					if(postfix[a] == NULL)
					{
						postfix[a] = ')';
						postfix[a + 1] = NULL;
						break;
					}
				}
			}


			// Is left paranthesis
			else if( isOperator(infix[a]) == -1)
			{
				// Push it onto the stack
				pCurrentNode = push('(',pCurrentNode);
			}

			// is operator
			else if( isOperator(infix[a]) == 1)
			{
				// If the top of the stack operator is equal or higher then the current operator
				while(pCurrentNode && precedence(pCurrentNode->data, infix[a]) >= 0)
				{	
					// Pop operators and insert the popped operators in postfix
					postfix[postCount] = stackTop(pCurrentNode);
					postCount++;
					pCurrentNode = pop(pCurrentNode);
				}
		

				// Push the current infix onto the stack
				pCurrentNode = push(infix[a],pCurrentNode);
			}

			// is right paranethesis
			else if( isOperator(infix[a]) == -2)
			{
				// Run while the top of the stack isnt a left parenthesis
				while(pCurrentNode->data != NULL && isOperator(pCurrentNode->data) != -1)
				{
					// Pop operators from the top of the stack and insert them in postfix
					postfix[postCount] = stackTop(pCurrentNode);
					postCount++;
					pCurrentNode = pop(pCurrentNode);
				}

				// Discard the left parenthesis from the stack
				pCurrentNode = pop(pCurrentNode);
			}

		}

	}

	printf("%s\n", infix);
	printf("%s\n", postfix);

	while(1);
    return 0;
}









stack* push(char data, stack* currentStack)
{
    stack* newStack =(stack*)malloc(sizeof(stack));

    // First in list give it a value
    if(currentStack == NULL || currentStack->data == NULL)
    {
        newStack->data = data;
        newStack->belowData = NULL;
        return newStack;
    }
	else
	{
		newStack->belowData = currentStack;
		newStack->data = data;
		currentStack = newStack;
		return currentStack;
	}
}

stack* pop(stack* currentStack)
{

    if(currentStack)
    {
		printf("Popped off: %c\n", currentStack->data);
		currentStack = currentStack->belowData;
    }
    else
    {
        printf("Stack is empty\n");
    }

    return currentStack;
    
}

int isOperator(char data)
{
	// If the infix is a number
	if(data >= '0' && data < '9')
	{
		return(0);
	}
	else if(data == '(') // infix is a left parenthesis
	{
		return(-1);
	}
	else if(data == ')') // infix is a right parenthesis
	{
		return(-2);
	}
	else // Infix is a Operation
	{
		return(1);
	}
}

int precedence(char operator1, char operator2)
{
	int operatorPrecedence[2];

	// Highest level operations
	if(operator1 == '*' || operator1 == '/' || operator1 == '%' || operator1 == '^')
	{
		operatorPrecedence[0] = 1;
	}
	else
	{
		operatorPrecedence[0] = 0;
	}

	// Highest level operations
	if(operator2 == '*' || operator2 == '/' || operator2 == '%' || operator2 == '^')
	{
		operatorPrecedence[1] = 1;
	}
	else
	{
		operatorPrecedence[1] = 0;
	}
	
	// Check whos precendence is higher
	if(operatorPrecedence[0] > operatorPrecedence[1])
	{
		// Operater 1 is greater then operator 2
		return(1);
	}
	else if (operatorPrecedence[0] < operatorPrecedence[1])
	{
		// Operater 1 is Lesser then operator 2
		return(-1);
	}
	else // Equal
	{
		// Operater 1 is equal to operator 2
		return(0);
	}
}


void  convertToPostfix(char infix[], char postfix[] )
{
	//printf("%s",operation);
}

char stackTop(stack* currentStack)
{
	 //If stacks not empty
	 if(currentStack )
	 {
		return(currentStack->data);
	 }
}

bool isEmpty(stack* currentStack)
{
	//If stacks not empty
	 if(currentStack )
	 {
		return(false);
	 }
	 else
	 {
		return(true);
	 }
}

void printStack(stack* currentStack)
{
	// Dont want to lose are place
	stack* newStack;
	newStack = currentStack;

	while(newStack)
	{
		printf("%c\n", currentStack->data);

		if(newStack->belowData)
		{
			newStack = newStack->belowData;
		}
	}
}s

[VictorN]

Did you try to debug your code to see what and where goes wrong?
Is there some important reason to write in plain C code and reinvent the wheel rather than use C++ with its STL library that contains stack and many other classes?

[Paul McKenzie]

The stack code i made at the start worked fine but now it assigns random values and goes NULL for no reason. I have changed a ton of the code to get past certain errors and now its just starting to fall apart.

Instead of changing code all over the place without any thought as to what you're doing, you must debug your code, and then after debugging, you make the appropriate changes. Never make changes to code until you are certain what those changes are and why those changes are being made.

Also, you're supposedly using Visual C++, so you use the debugger that comes with the compiler to single-step through your program and determine exactly what is wrong and exactly what needs to be done to fix the problem.

Any ideas on how i could get this working? I am considering just scrapping the entire thing and starting fresh. Am

Start fresh by writing down exactly what steps need to be done. Go through those steps by hand, making sure you know that they produce the correct results. Do not try to work out these steps by writing a program. If you're trying to figure out what to do by writing code, you're going to lose.

Second, learn how to translate those steps into a C++ program. The program you wrote looks like 'C' code, and has errors that have nothing to do with Infix/Postfix.

	stack* pCurrentNode = (stack*)malloc(sizeof(stack));

1) Why are you using malloc() in a C++ program?

2) Why even dynamically allocate here in the first place?

	stack pCurrentNode;

That's all you need to do. Then you change -> to "." notation. This also gets rid of the memory leak in your program.

As Victor pointed out, is the goal of the program to perform Infix to Postfix, or to write a stack data structure using low-level 'C' coding techniques? You already have a stack class in C++, so why not use that to get you closer to the goal of writing the Infix to Postfix program? You would then have one thing less to worry about, and that is whether the stack class is faulty.

Regards,

Paul McKenzie