Antoun J. Yaacoub Ph.D.

We are interested in evaluating mathematical expressions containing different operators and integer operands. Mathematical expressions are usually written in infix notation, and in order to the computer to evaluate its value, it needs to rewrite the expression in postfix notation. So your job is to read an infix expression, then convert it to a postfix expression, then evaluate the resulting postfix expression.

The input expression is a string composed of digits (0 till 9) and operators (/, *, -, +, ^ (denotes exponentiation) and # (denotes unary minus)). The output should be the value of the postfix expression.

Examples:

$\begin{array}{ | c | c | c | } \hline \textbf{Infix Expression} & \textbf{Postfix Expression} & \textbf{Value} \\ \hline ((6 - (2 + 3)) * (3 + 8 / 2)) \land 2 + 3 & 6 2 3 + - 3 8 2 / + * 2 \land 3 + & 52 \\ \hline 7-( \#( \#(2 + 3))) \land 2 & 7 2 3 + \# \# 2 \land - & -18 \\ \hline \end{array}$

Difficulty level

This exercise is mostly suitable for students

#include<stdio.h>
#include<string.h>
#define N 1000
typedef float  element;
typedef struct {
	element data[N];
	int top;
} stack;

stack CreateStack()
{
	stack p;
	p.top = -1;
	return p;
}

int isEmptyStack(stack p)
{
	return (p.top == -1);
}

int isFullStack(stack p)
{
	return (p.top == N - 1);
}

int Push(stack *p, element e)
{
	if (isFullStack(*p)) return 0;
	p->data[++p->top] = e;
	return 1;
}

int Pop(stack *p)
{
	if (isEmptyStack(*p)) return 0;
	p->top--;
	return 1;
}

int Top(stack p, element *e)
{
	if (isEmptyStack(p)) return 0;
	*e = p.data[p.top];
	return 1;
}


int is_digit(char c)
{
	return (c >= '0' && c <= '9');
}


float to_digit(char c)
{
	return (float)(c - '0');
}

int stackable(char o1, char o2)
{
	switch (o1)
	{
	case '(': return 1;
	case '+': case '-': return (o2 == '(');
	case '#': return (o2 != '#');
	case '*':case '/': return (o2 == '(' || o2 == '+' || o2 == '-');
	case '^': return (o2 != '#' && o2 != '^');
	case ')': return (o2 == '(');
	}
}

int is_operator(char c)
{
	return (c == '*' || c == '-' || c == '/' || c == '+' || c == '^' || c == '#' || c == ')' || c == '(');
}


float power(float X, float M)
{
	if (M == 0) return 1;
	if (M<0) return 1. / power(X, -M);
	return X*power(X, M - 1);
}

float operation(float nb1, char c, float nb2)
{
	switch (c)
	{
	case '+': return nb1 + nb2;
	case '-': return nb1 - nb2;
	case '*': return nb1*nb2;
	case '/': return nb1 / nb2;
	case '^': return power(nb1, nb2);
	case '#': return -nb1;
	}
}

void infix_to_postfix(char *infix, char *postfix)
{
	stack s = CreateStack();
	element e;
	int i, j;

	j = 0;
	for (i = 0; i<strlen(infix); i++)
	{
		if (is_digit(infix[i]))
			postfix[j++] = infix[i];
		else
			if (is_operator(infix[i]))
			{
				while (Top(s, &e) == 1 && !stackable(infix[i], e))
				{
					Pop(&s);
					postfix[j++] = e;
				}
				if (isEmptyStack(s) || infix[i] != ')')
					Push(&s, infix[i]);
				else
					Pop(&s);
			}
	}
	while (Top(s, &e) == 1)
	{
		Pop(&s);
		postfix[j++] = e;
	}
	postfix[j] = '\0';
}


float result(char *str)
{
	element opnd2, opnd1, value;
	int i;

	stack s2 = CreateStack();

	for (i = 0; str[i]; i++)
	{
		if (is_digit(str[i]))
			Push(&s2, to_digit(str[i]));
		else
		{
			if (str[i] != '#')
			{
				Top(s2, &opnd2); Pop(&s2);
				Top(s2, &opnd1); Pop(&s2);
				value = operation(opnd1, str[i], opnd2);
			}
			else
			{
				Top(s2, &opnd2); Pop(&s2);
				value = operation(opnd2, str[i], opnd2);
			}
			Push(&s2, value);
		}
	}

	Top(s2, &value);
	return value;
}



int main()
{
	int tests, size, i;
	char str[N], R1[N];

	// read nb of tests
	scanf("%d", &tests);

	// each line: an infix expression 
	while (tests--)
	{
		scanf("%s", str);
		infix_to_postfix(str, R1);
		printf("%.4f\n", result(R1));
	}
	return 0;
}

Back to the list of exercises

Looking for a more challenging exercise, try this one !!

Removing a sequence of 3 characters from a string

Infix to Postfix Expression and Evaluation