VTU-DS-Lab-Program/04.InfixToPostfixConversion.c at master · ShivamNagpal/VTU-DS-Lab-Program · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
4 Design, Develop and Implement a Program in C for converting an Infix
Expression to Postfix Expression. Program should support for both
parenthesized and free parenthesized expressions with the operators: +, -, *,/,
 %(Remainder), ^(Power) and alphanumeric operands.
*/

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

typedef enum {lparen, rparen, plus, minus, mul, divi, mod, pwr, eos, operand} precedence;

precedence getToken(char infix[], char *symbol, int *n);
void convert(char infix[]);
void push(int stack[], int *top, precedence token);
precedence pop(int stack[], int *top);
void printToken(precedence token);

void main()
{
	char infix[30];
	printf("Enter Infix Expression\n");
	gets(infix);
	convert(infix);
}

precedence getToken(char infix[], char *symbol, int *n)
{
	*symbol = infix[(*n)++];
	switch(*symbol)
	{
		case '(':	return lparen;
		case ')':	return rparen;
		case '+':	return plus;
		case '-':	return minus;
		case '*':	return mul;
		case '/':	return divi;
		case '%':	return mod;
		case '^':	return pwr;
		case '\0':	return eos;
		default:	return operand;
	}
}

void convert(char infix[])
{
	int stack[20], top = 0, n=0;
	int icp[] = {5, 4, 1, 1, 2, 2, 2, 3, 0};
	int isp[] = {0, 4, 1, 1, 2, 2, 2, 3, 0};
	precedence token;
	char symbol;
	stack[0] = eos;
	for(token = getToken(infix, &symbol, &n); token != eos; token = getToken(infix, &symbol, &n))
	{
		if(token == operand)
			printf("%c", symbol);
		else if(token == rparen)
		{
			while(stack[top] != lparen)
			{
				printToken(pop(stack, &top));
			}
			pop(stack, &top);
		}
		else
		{
			while(isp[stack[top]] >= icp[token])
			{
				printToken(pop(stack, &top));
			}
			push(stack, &top, token);
		}
	}
	while(stack[top] != eos)
	{
		printToken(pop(stack, &top));
	}
}

void push(int stack[], int *top, precedence token)
{
	stack[++(*top)] = token;
}

precedence pop(int stack[], int *top)
{
	return stack[(*top)--];
}

void printToken(precedence token)
{
	switch(token)
	{
		case plus:
			printf("+");
			break;
		case minus:
			printf("-");
			break;
		case mul:
			printf("*");
			break;
		case divi:
			printf("/");
			break;
		case mod:
			printf("%c", '%');
			break;
		case pwr:
			printf("^");
			break;
	}
}