infix to postfix Archives - C Program Examples

Infix to postfix conversion and postfix expression evaluation. In this C Program, we take an infix expression as input from the user and convert it in to a postfix expression using a stack. Then we evaluate that postfix expression to obtain the result.

Problem Statement

Write a C Program to convert a given infix expression to postfix and evaluate it. Infix expression is the most commonly used expression and we are all familiar with this. In Infix expression, the operator is between two operands, as in 1 + 2, or “5 + ((2 + 6) × 9) − 8”. In Postfix expression, also called as Reverse Polish Notation or postorder expression, operators are written after their operands. For example the above expressions become 12+ and 526+9*+8- respectively when written in postfix notation.

Read more about Infix, Postfix and Prefix

The Solution

The problem is divided into two tasks. First, the given infix expression is converted to a postfix expression. Then we take that postfix expression and evaluate it. In C Program Examples website, we have already given programs to do these things separately. You can see them here and here.

Here we are doing it in a single program. This is in response to a request from one of our readers in a recent comment.

The Program

	/*
	* C Program to convert a given infix expression to postfix expression and evaluate it.
	* (c) www.c-program-example.com
	*/

	#define SIZE 50 /* Size of Stack */
	#include <ctype.h>
	#include <stdio.h>

	char s[SIZE];
	int top = -1; /* Global declarations */

	/* Function to remove spaces from given string */
	void RemoveSpaces(char* source) {
	char* i = source;
	char* j = source;
	while(*j != 0) {
	i = j++;
	if(*i != ' ')
	i++;
	}
	*i = 0;
	}

	/* Function for PUSH operation */
	void push(char elem) {
	s[++top] = elem;
	}

	/* Function for POP operation */
	char pop() {
	return (s[top--]);
	}

	/* Function for precedence */
	int pr(char elem) {
	switch (elem) {
	case '#':
	return 0;
	case '(':
	return 1;
	case '+':
	case '-':
	return 2;
	case '*':
	case '/':
	return 3;
	}
	}

	/*
	* Function to convert from infix to postfix expression
	*/
	void infix_to_postfix(char infix, char postfix) {
	char ch, elem;
	int i = 0, k = 0;

	RemoveSpaces(infix);
	push('#');

	while ((ch = infix[i++]) != '\n') {
	if (ch == '(')
	push(ch);
	else if (isalnum(ch))
	postfix[k++] = ch;
	else if (ch == ')') {
	while (s[top] != '(')
	postfix[k++] = pop();
	elem = pop(); /* Remove ( */
	} else { /* Operator */
	while (pr(s[top]) >= pr(ch))
	postfix[k++] = pop();
	push(ch);
	}
	}

	while (s[top] != '#') /* Pop from stack till empty */
	postfix[k++] = pop();

	postfix[k] = 0; /* Make postfix as valid string */
	}

	/*
	* Function to evaluate a postfix expression
	*/
	int eval_postfix(char *postfix) {
	char ch;
	int i = 0, op1, op2;
	while((ch = postfix[i++]) != 0) {
	if(isdigit(ch))
	push(ch-'0'); /* Push the operand */
	else { /* Operator,pop two operands */
	op2 = pop();
	op1 = pop();
	switch(ch) {
	case '+' : push(op1+op2);
	break;
	case '-' : push(op1-op2);
	break;
	case '' : push(op1op2);
	break;
	case '/' : push(op1/op2);
	break;
	}
	}
	}
	return s[top];
	}

	void main() { /* Main Program */

	char infx[50], pofx[50];
	printf("\nInput the infix expression: ");
	fgets(infx, 50, stdin);

	infix_to_postfix(infx, pofx);

	printf("\nGiven Infix Expression: %sPostfix Expression: %s", infx, pofx);
	top = -1;
	printf("\nResult of evaluation of postfix expression : %d", eval_postfix(pofx));
	}

view raw Infix_postfix_eval.c hosted with ❤ by GitHub

Sample Output

Infix to postfix conversion and evaluation

Related Programs

/***********************************************************
* You can use all the programs on www.c-program-example.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact [email protected]
* To find more C programs, do visit www.c-program-example.com
* and browse!
*
* Happy Coding
***********************************************************/

#define SIZE 50 /* Size of Stack */
#include <ctype.h>
char s[SIZE];
int top = -1; /* Global declarations */

push(char elem) { /* Function for PUSH operation */
s[++top] = elem;
}

char pop() { /* Function for POP operation */
return (s[top--]);
}

int pr(char elem) { /* Function for precedence */
switch (elem) {
case '#':
return 0;
case '(':
return 1;
case '+':
case '-':
return 2;
case '*':
case '/':
return 3;
}
}

main() { /* Main Program */
char infx[50], pofx[50], ch, elem;
int i = 0, k = 0;
printf("nnRead the Infix Expression ? ");
scanf("%s", infx);
push('#');
while ((ch = infx[i++]) != '') {
if (ch == '(')
push(ch);
else if (isalnum(ch))
pofx[k++] = ch;
else if (ch == ')') {
while (s[top] != '(')
pofx[k++] = pop();
elem = pop(); /* Remove ( */
} else { /* Operator */
while (pr(s[top]) >= pr(ch))
pofx[k++] = pop();
push(ch);
}
}
while (s[top] != '#') /* Pop from stack till empty */
pofx[k++] = pop();
pofx[k] = ''; /* Make pofx as valid string */
printf("nnGiven Infix Expn: %s Postfix Expn: %sn", infx, pofx);
}

C Program Examples

infix to postfix

C Program For Infix To Postfix Conversion and Evaluation of postfix expression

Problem Statement

The Solution

The Program

Sample Output

Related Programs

C Program for Infix to Postfix Conversion.