Object NO.
- 8 9-Nov-23
Write a C Program to Implement Operator Precedence parser:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX_STACK_SIZE 100
int precedence[128] =
{
['+'] = 1,
['-'] = 1,
['*'] = 2,
['/'] = 2,
['^'] = 3,
};
struct Stack
{
char items[MAX_STACK_SIZE];
int top;
};
void initStack(struct Stack* stack)
{
stack->top = -1;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
void push(struct Stack* stack, char item)
{
if (stack->top < MAX_STACK_SIZE - 1)
{
stack->items[++stack->top] = item;
}
else
{
printf("Stack overflow\n");
exit(EXIT_FAILURE);
}
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
{
return stack->items[stack->top--];
}
else
{
printf("Stack underflow\n");
exit(EXIT_FAILURE);
}
}
int getPrecedence(char operator)
{
return precedence[(int)operator];
}
void operatorPrecedenceParser(char input[])
{
struct Stack stack;
initStack(&stack);
int i = 0;
while (input[i] != '\0')
{
if (isalnum(input[i]))
{
printf("%c ", input[i]);
}
else
{
while (!isEmpty(&stack) && getPrecedence(input[i]) <=
getPrecedence(stack.items[stack.top]))
{
printf("%c ", pop(&stack));
}
push(&stack, input[i]);
}
i++;
}
while (!isEmpty(&stack))
{
printf("%c ", pop(&stack));
}
printf("\n");
}
int main()
{
char input[100];
printf("Enter an expression: ");
fgets(input, sizeof(input), stdin);
printf("Operator Precedence Parsing: ");
operatorPrecedenceParser(input);
return 0;
}
Output:
a+b*c–d
Enter an expression: a + b * c – d
Operator Precedence Parsing: a b c * + d -
