#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
typedef struct stack *Stack;
typedef struct node *Node;
Stack createStack();
int isEmpty(Stack stack);
int pushItem(Stack stack, char item);
char popItem(Stack stack);
int priority(char);
char *processExpression(char *expression);
struct node {
char value;
Node next;
};
struct stack {
Node head;
};
Stack createStack(){
Stack stack = malloc(sizeof(Stack));
if (stack == NULL)
return NULL;
stack->head = NULL;
return stack;
}
int isEmpty(Stack stack){
assert(stack!=NULL);
return stack->head == NULL;
}
int pushItem(Stack stack, char item){
assert(stack != NULL);
Node node = malloc(sizeof(Node));
if (node == NULL)
return 0;
node->value=item;
node->next=stack->head;
stack->head=node;
return 1;
}
char popItem(Stack stack){
assert(stack!=NULL);
if (stack->head ==NULL)
return '\n';
Node node = stack->head->next;
char item = stack->head->value;
free(stack->head);
stack->head=node;
return item;
}
int priority(char item){
switch (item){
case '*':
case '/':
return 3;
case '-':
case '+':
return 2;
case '(':
return 1;
}
}
char *processExpression(char *expression){
Stack stack = createStack();
char c;
char *output = calloc(sizeof(char),80);
int k,point;
k = point=0;
c = expression[k];
while (c!='\0'){
if (c==')'){
while (stack->head->value!='(')
output[point++]=popItem(stack);
popItem(stack);
}
if (c>='a' && c<='z')
output[point++]=c;
if (c=='(')
pushItem(stack,'(');
if (c=='+'||c=='-'||c=='*'||c=='/'){
if (isEmpty(stack))
pushItem(stack,c);
else{
while(!isEmpty(stack)&&(priority(stack->head->value)>=priority(c)))
output[point++]=popItem(stack);
pushItem(stack,c);
}
}
k++;
c = expression[k];
}
while (stack->head!=NULL)
output[point++]=popItem(stack);
output[point]='\0';
free(stack);
return output;
}
int main(){
printf("a+b=%s\n",processExpression("a+b\0"));
printf("(a+b)*(c-d)-e=%s\n", processExpression("(a+b)*(c-d)-e\0"));
printf("a+b*c/(d-e)*f=%s\n", processExpression("a+b*c/(d-e)*f\0"));
return 0;
}