char_stack.h
typedef struct stack
{
char *values;
int maxSize;
int top;
}stack;
stack * createstack(int maxElements)
{
//create stack
stack *s;
s = (stack *)malloc(sizeof(stack));
//initialize
s->values = (char *)malloc(sizeof(char)*maxElements);
s->top = -1;
s->maxSize = maxElements;
//return
return s;
}
void push(stack *s, char n)
{
if(s->top == s->maxSize)
{
printf("stack is Full\n");
}
else
{
printf("Pushing Value:%c\n",n);
//increament first then push
++s->top;
s->values[s->top] = n;
}
return;
}
char pop(stack *s)
{
char value;
if(s->top == -1)
{
printf("stack is Empty\n");
}
else
{
//remove first then decrement
value = s->values[s->top];
s->top--;
printf("Poping value:%c\n",value);
}
return value;
}
int isEmpty(stack *s)
{
if(s->top == -1)
return 1;
else
return 0;
}
void display(stack *s)
{
int i=0;
for(i=0;i<=s->top;i++)
{
printf("%c",s->values[i]);
}
}
Postfix.c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "char_stack.h"
#define SIZE 30
#define OPERAND 100
int priority(char c)
{
int priority;
switch(c){
case '^':
priority = 4;
break;
case '/':
case '*':
priority = 3;
break;
case '+':
case '-':
priority = 2;
break;
case '(':
priority = 1;
break;
case '$':
priority = 0;
break;
default:
//default operand
priority = OPERAND;
break;
}
return priority;
}
char *inTopost(char *infix)
{
int i = 0;
char x;
//init postfix
char *postfix = (char*)malloc( SIZE *sizeof(char));
//init stack
stack *s = createstack(SIZE);
//push $ as starting char
push(s,'$');
//postfix counter
int j = 0;
//iterate over infix
for (i = 0; i < strlen(infix); i++){
//get infix charcter
char in = infix[i];
printf("%d.Character:%c\n",i+1,in);
//get top of stack character
char tos = s->values[s->top];
//check infix character
//if input character is '(' push it
if(in=='(')
{
push(s,in);
}
//if input character is ')' then pop all character till ')'
else if(in== ')')
{
while((x=pop(s))!='(')
{
postfix[j++]=x;
}
}
//if infix character priority=-1 then it is operand
else if(priority(in)==OPERAND)
{
//if operand to directly move to postfix
postfix[j++]= in;
}
//else check priority of stack character and infix character
else if(priority(in) > priority(tos)){
//if priority of infix is greater then or equal to infix then push character to stack
push(s,in);
}
//else pop all the from stack till infix priority is less or equal than stack
//and push infix character
else{
while(priority(in) <= priority(tos))
{
postfix[j++] = pop(s);
tos = s->values[s->top];
}
push(s,in);
}
printf(" %-27s",postfix);
display(s);
printf("\n\n");
}
//pop all stack character till its not '$'
while((x=pop(s))!='$')
{
postfix[j++]=x;
}
// return postfix string
return postfix;
}
int main()
{
//initialize array
char *infix;
//read value
infix = "(A+B)*D+E/(F+G*D)+C";
//scanf("%s",infix);
//convert to postfix
char *postfix = inTopost(infix);
//print postfix value
printf("%s\n", postfix);
return 0;
}
0 comments:
Post a Comment