Your job is to read a postfix expression, convert it into an expression tree and then evaluate the tree.

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<stdlib.h>
#include<string.h>
#define N 1000
typedef char element1;



typedef struct node
{
    element1 data;
    struct node *left,*right;
} *Tree;
typedef Tree Btree;

Btree Construct(element1 e, Btree L, Btree R)
{
    Btree temp;
    temp = (Btree) malloc(sizeof(struct node));
    if(!temp) return 0;
    temp->data=e;
    temp->left=L;
    temp->right=R;
    return temp;
}


typedef Tree 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 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 -nb2;
    }
    return 0;
}

Btree Build(char *postfix)
{
    int i;
    Btree new=NULL, new1=NULL, new2=NULL;
    stack s = CreateStack();
    for(i=0 ; postfix[i]; i++)
    {
       // printf("%c\n", postfix[i]);
        if(!is_operator(postfix[i])) // operand
        {
            new = (Btree)malloc(sizeof(struct node));
            if(!new) return NULL;
            new->data=postfix[i];
            new->left=new->right = NULL;
            Push(&s,new);
        }
        else
        {
            new = (Btree)malloc(sizeof(struct node));
            if(!new) return NULL;
            new->data=postfix[i];
            
            Top(s,&new1); Pop(&s);
            new->right=new1;
            new->left=NULL;
            if(postfix[i]!='#')
            {
                Top(s,&new2); 
                Pop(&s);
                new->left=new2;
            }
            
            Push(&s,new);
        }
    }
    Top(s,&new); Pop(&s);
    return new;
}

float result(Btree B)
{
    float  vl, vr;
    if(!B) return 0;
    if(!B->left && !B->right) 
        return to_digit(B->data);
    vl = result(B->left);
    vr = result(B->right);
    return operation(vl, B->data, vr);
}


int main()
{
    int tests;
    char str[N];
    Btree B;

    // read nb of tests
    scanf("%d", &tests);

    // each line: a postfix expression 
    while (tests--)
    {
        B=NULL;
        scanf("%s", str);
        B=Build(str);
        printf("%.4f\n", result(B));
    }
    return 0;
}
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Sorting using the radix sort algorithm