Using stack and binary search tree to convert postfix expression to infix

Monday, May 5, 2014

I am attempting to write a program which will take as argument an expression in postfix (reverse polish notation) and use a binary search tree to output the syntax in infix notation. So far my program works but due to the way I wrote it it will not work with expressions involving operand of more than two digits (ex. 5 10 +). I was hoping someone might suggest an alternate method that will allow this to work for a wider variety of expressions. I have given this some thought and know my problem lies with using the character data type in my tree structure however I have been unable to think of a better way. Any help would be greatly appreciated. I plan to also make the program evaluate the expression however I am undecided whether to use the tree to do this or just use the stack. Also please excuse my error ridden comments, this is still a WIP. Here is my code



#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct stacknode {
char data;
struct stacknode * next;
} sNode;

typedef struct bstnode{
char data;
struct bstnode * right;
struct bstnode * left;
} bst;

sNode * push(sNode * top, char data);
sNode * pop(sNode * top);
char peek(sNode * top);
int power(int x, unsigned int y);
bst* newnode(char data);
void inorder(bst* root);

int main(int argc, char * argv[]){
int i;

sNode * stack = (sNode*)malloc(sizeof(sNode));
stack = NULL;
bst * leaftemp;
bst * root = (bst*)malloc(sizeof(bst));
root = NULL;
char * end;

if (argc < 2){
fputs("Too few arguments, please try again\n", stderr);
}

for (i = 1; i < argc; i++){//Go through arguments
if (isdigit((unsigned char)*argv[i])){//If it's a digit, push it on the stack
stack = push(stack, *argv[i]);
}
else{
if (root == NULL){
root = newnode(*argv[i]);
if (stack == NULL){ fputs("Invalid expression!\n", stderr); return 1; }
root->right = newnode(peek(stack));
stack = pop(stack);
if (stack == NULL){ fputs("Invalid expression!\n", stderr); return 1; }
root->left = newnode(peek(stack));
stack = pop(stack);
}
else {
leaftemp = newnode(*argv[i]);
leaftemp->left = root;
leaftemp->right = newnode(peek(stack));
stack = pop(stack);
root = leaftemp;
}
}
}

printf("Postfix: ");
for (i = 1; i < argc; i++){
printf("%c ", *argv[i]);
}
printf("\n");
printf("Infix: ");
inorder(root);
printf("\n");
printf("Evaluated: ");

printf("\n");

return 0;
}

//Function push
//Function takes a pointer to the top of a stack node and and integer containing
//the data to be pushed onto the stack
sNode * push(sNode * top, char data){
sNode * new;//Make and size a new node
new = (sNode*)malloc(sizeof(sNode));
if (top == NULL){//If this is the first node do this
new->data = data;
new->next = NULL;
return new;
}
else{//If this is not the first put it on top
new->data = data;
new->next = top;
return new;
}
}
//Function pop
//Function takes a pointer to a node on the top of a stack and pops the top node
//off of that stack
sNode * pop(sNode * top){
if (top == NULL){//If stack is empty return null
return top;
}
else {//Take the top node off and make the one below it the top
sNode * temp = (sNode*)malloc(sizeof(sNode));
temp = top;
top = temp->next;
free(temp);
return top;
}
}

//Function peek
//Function takes a pointer to a node on the top of a stack and returns the data
//contained in that top node
char peek(sNode * top){
if (top == NULL){//If stack is empty return null
return '\0';
}
else{//Return the data
return top->data;
}
}

//Function power
//Function takes an integer representing a number and an unsigned integer
//representing the power the first integer should be raised to
int power(int x, unsigned int y){
if (y == 0)
return 1;
else if (y % 2 == 0)
return power(x, y / 2)*power(x, y / 2);
else
return x*power(x, y / 2)*power(x, y / 2);
}

//Function newnode
//Function takes data in the form of an integer and returns the address
//of a new tree node containing that data
bst* newnode(char data){
bst* new = (bst*)malloc(sizeof(bst)); //Make and size node
new->data = data; //Insert data
new->left = NULL; //Set pointers to NULL
new->right = NULL;

return new; //Return address of new node
}

void inorder(bst* root){ //Left, root, right
if (root == NULL) return;
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}






http://ift.tt/1lTExE0