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

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(op1*op2);
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

C Program for Infix to Postfix Conversion.

C Program for Infix to Postfix Conversion. Here we covert the infix expression to postfix expression by using stack. for example a*b-c/d is the infix expression, and equivalent postfix expression is: ab*cd/-. Read more about C Programming Language .

/***********************************************************
* 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 info@c-program-example.com
* 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);
}

Read more Similar C Programs
Data Structures

Learn C Programming

You can easily select the code by double clicking on the code area above.

To get regular updates on new C programs, you can Follow @c_program

You can discuss these programs on our Facebook Page. Start a discussion right now,

our page!

Share this program with your Facebook friends now! by liking it

(you can send this program to your friend using this button)

Like to get updates right inside your feed reader? Grab our feed!

(c) www.c-program-example.com