Postfix evaluation in C

Introduction

In this lesson, we aim to enhance your understanding of postfix evaluation in the C programming language. We will dive deep into postfix notation, scrutinize its relevance, and dissect practical examples of applying postfix evaluation in C.

Overview

In the course of this tutorial, we will introduce postfix notation, explore why it holds significance, and give hands-on postfix evaluation examples in C using an array. We will wrap up with a summary and answer some FAQs.

What is Postfix Notation?

In the realm of computer programming, specifically in C language, postfix notation is a method used to write arithmetic expressions. Unlike in infix notation, where the operator is placed between operands, in postfix notation, the operator is placed after the operands, making it ideal for stack operations. Postfix notation eliminates the need for parentheses to indicate the operation order. For example, in infix notation, an expression like (A+B)C is written as AB+C in postfix notation.

Conversion from infix to postfix notation can be accomplished using a stack data structure. The operands are printed while the operators are pushed to the stack. If the scanned character is an ‘)’, the stack elements are popped and printed until an ‘(‘ is encountered.

Why Postfix?

The significance of postfix notation lies in its operational efficiency and simplicity. When compared to other notations, such as infix and prefix, postfix notation simplifies complex mathematical expressions and makes evaluation easy. It removes ambiguity and the necessity for operator precedence rules. Moreover, postfix expressions can be evaluated efficiently using a stack, which is a fundamental data structure in C programming.

In C language, where stack operations are widely used, the efficiency of postfix notation becomes quite visible. For instance, in the evaluation of arithmetic expressions, the postfix notation uses a simple algorithm, easily implemented using a stack. This straightforwardness and efficiency are why postfix notation is so essential to C programming.

Steps to Convert Infix to Postfix

Converting infix expressions to postfix expressions is a process known as the Shunting Yard algorithm. It involves using stacks to rearrange the operators and operands to create the postfix expression. Here are the steps to convert an infix expression to postfix:

1. Initialize two empty stacks: one for operators and one for the output (postfix expression).
2. Scan the infix expression from left to right, one character at a time.
3. If the scanned character is an operand (number or variable), add it to the output.
4. If the scanned character is an open parenthesis '(', push it onto the operator stack.
5. If the scanned character is a closing parenthesis ')', pop operators from the operator stack and add them to the output until an open parenthesis '(' is encountered on the top of the operator stack. Pop and discard the open parenthesis.
6. If the scanned character is an operator (+, -, *, /, etc.), then:

a). While the operator stack is not empty and the top of the operator stack has higher or equal precedence to the current operator, pop the top operator from the operator stack and add it to the output.

b). Push the current operator onto the operator stack.

7. After scanning all the characters, pop any remaining operators from the operator stack and add them to the output.
8. The final output on the postfix stack is the converted postfix expression.

Example: 4 + 7 - 5 / 6

Here is an example of converting expressions from infix to postfix:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_EXPR_SIZE 100

int precedence(char operator)
{
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return -1;
}
}

int isOperator(char ch)
{
return (ch == '+' || ch == '-' || ch == '*' || ch == '/'
|| ch == '^');
}

char* infixToPostfix(char* infix)
{
int i, j;
int len = strlen(infix);
char* postfix = (char*)malloc(sizeof(char) * (len + 2));
char stack[MAX_EXPR_SIZE];
int top = -1;

for (i = 0, j = 0; i < len; i++) {
if (infix[i] == ' ' || infix[i] == '\t')
continue;

if (isalnum(infix[i])) {
postfix[j++] = infix[i];
} else if (infix[i] == '(') {
stack[++top] = infix[i];
} else if (infix[i] == ')') {
while (top > -1 && stack[top] != '(')
postfix[j++] = stack[top--];
if (top > -1 && stack[top] != '(')
return "Invalid Expression";
else
top--;
} else if (isOperator(infix[i])) {
while (top > -1 && precedence(stack[top]) >= precedence(infix[i]))
postfix[j++] = stack[top--];
stack[++top] = infix[i];
}
}

while (top > -1) {
if (stack[top] == '(') {
return "Invalid Expression";
}
postfix[j++] = stack[top--];
}
postfix[j] = '\0';
return postfix;
}

int main()
{
char infix[MAX_EXPR_SIZE] = "x+y*(z^p-n)^(o+u*t)-j";
char* postfix = infixToPostfix(infix);
printf("%s\n", postfix);
free(postfix);
return 0;
}

Postfix Evaluation Calculator

Code:

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

struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    if (!stack)
        return NULL;
    stack->top = -1;
    stack->capacity = capacity;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    if (!stack->array)
        return NULL;
    return stack;
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

char peek(struct Stack* stack) {
    return stack->array[stack->top];
}

char pop(struct Stack* stack) {
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$';
}

void push(struct Stack* stack, char op) {
    stack->array[++stack->top] = op;
}

int evaluatePostfix(char* exp) {
    struct Stack* stack = createStack(strlen(exp));
    int i;
    if (!stack)
        return -1;
    for (i = 0; exp[i]; ++i) {
        if (isdigit(exp[i]))
            push(stack, exp[i] - '0');
        else {
            int val1 = pop(stack);
            int val2 = pop(stack);
            switch (exp[i]) {
                case '+':
                    push(stack, val2 + val1);
                    break;
                case '-':
                    push(stack, val2 - val1);
                    break;
                case '*':
                    push(stack, val2 * val1);
                    break;
                case '/':
                    push(stack, val2 / val1);
                    break;
            }
        }
    }
    return pop(stack);
}

int main() {
    char exp[] = "321*+7-";
    printf("postfix evaluation: %d", evaluatePostfix(exp));
    return 0;
}

How to Evaluate a Postfix Expression Using Stack?

Code:

#include <stdio.h>
#include <ctype.h>
#define MAXSTACK 100
#define POSTFIXSIZE 100
int stack[MAXSTACK];
int top = -1;
void push(int item)
{
    if (top >= MAXSTACK - 1) {
        printf("stack over flow");
        return;
    } else {
        top = top + 1;
        stack[top] = item;
    }
}
int pop()
{
    int item;
    if (top < 0) {
        printf("stack under flow");
    } else {
        item = stack[top];
        top = top - 1;
        return item;
    }
}
void EvalPostfix(char postfix[])
{
    int i;
    char ch;
    int val;
    int A, B;

    for (i = 0; postfix[i] != ')'; i++) {
        ch = postfix[i];
        if (isdigit(ch)) {
            push(ch - '0');
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            A = pop();
            B = pop();

            switch (ch) {
                case '*':
                    val = B * A;
                    break;
                case '/':
                    val = B / A;
                    break;
                case '+':
                    val = B + A;
                    break;
                case '-':
                    val = B - A;
                    break;
            }

            push(val);
        }
    }
    printf(" \n Result of expression evaluation : %d \n", pop());
}
int main()
{
    int i;
    char postfix[POSTFIXSIZE];
    printf("ASSUMPTION: There are only four operators(*, /, +, -) in an expression and operand is single digit only.\n");
    printf(" \nEnter postfix expression,\npress right parenthesis ')' for end expression : ");
    for (i = 0; i <= POSTFIXSIZE - 1; i++) {
        scanf("%c", &postfix[i]);
        if (postfix[i] == ')') {
            break;
        }
    }
    EvalPostfix(postfix);
    return 0;
}

Implementation of the Algorithm

• Java Implementation

Code:

import java.util.Stack;

public class Test {
    static int evaluatePostfix(String exp) {
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);

            if (Character.isDigit(c))
                stack.push(c - '0');
            else {
                int val1 = stack.pop();
                int val2 = stack.pop();

                switch (c) {
                    case '+':
                        stack.push(val2 + val1);
                        break;
                    case '-':
                        stack.push(val2 - val1);
                        break;
                    case '/':
                        stack.push(val2 / val1);
                        break;
                    case '*':
                        stack.push(val2 * val1);
                        break;
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String exp = "432*+7-";
        System.out.println("postfix evaluation: " + evaluatePostfix(exp));
    }
}

• C++ Implementation

Code:

#include <bits/stdc++.h>
using namespace std;

int evaluatePostfix(string exp)
{
stack<int> st;

for (int i = 0; i < exp.size(); ++i) {
if (isdigit(exp[i]))
st.push(exp[i] - '0');
else {
int val1 = st.top();
st.pop();
int val2 = st.top();
st.pop();
switch (exp[i]) {
case '+':
st.push(val2 + val1);
break;
case '-':
st.push(val2 - val1);
break;
case '*':
st.push(val2 * val1);
break;
case '/':
st.push(val2 / val1);
break;
}
}
}
return st.top();
}

int main()
{
string exp = "532*+14-";
cout << "postfix evaluation: " << evaluatePostfix(exp);
return 0;
}

• Python Implementation

Code:

class Evaluate:

    def __init__(self, capacity):
        self.top = -1
        self.capacity = capacity
        self.array = []

    def isEmpty(self):
        return True if self.top == -1 else False

    def peek(self):
        return self.array[-1]

    def pop(self):
        if not self.isEmpty():
            self.top -= 1
            return self.array.pop()
        else:
            return "$"

    def push(self, op):
        self.top += 1
        self.array.append(op)

    def evaluatePostfix(self, exp):
        for i in exp:
            if i.isdigit():
                self.push(i)
            else:
                val1 = self.pop()
                val2 = self.pop()
                self.push(str(eval(val2 + i + val1)))
        return int(self.pop())

if __name__ == '__main__':
    exp = "332*+10-"
    obj = Evaluate(len(exp))
    print("postfix evaluation: %d" % (obj.evaluatePostfix(exp)))

Limitation of the Previous Approach

The postfix evaluation approach has several advantages, such as simplicity, no need for parentheses, and easy implementation using a stack. However, it also has some limitations, which are important to consider:

Lack of Readability: Postfix expressions can become challenging to read and understand, especially for complex expressions. The absence of parentheses and the need to mentally track the operands and operators' order might make the expression harder to interpret and maintain.

Conversion Overhead: Converting infix expressions to postfix can add an extra step before evaluation. This conversion process can increase the time complexity of evaluating the expression. While the conversion is generally efficient, it's still an additional step that may not be needed in other evaluation approaches.

Limited Operator Support: The postfix evaluation approach inherently works well with binary operators (+, -, *, /) but may become more complicated when dealing with unary operators or more complex expressions that involve functions or multiple variables.

Error Handling: In postfix evaluation, there is no easy way to catch and handle certain errors, such as division by zero or invalid expressions. The algorithm assumes a valid postfix expression, so additional validation and error handling might be needed.

Infix to Postfix Conversion: If you are starting with an infix expression, you need to first convert it to postfix to use the postfix evaluation approach. While this conversion is relatively straightforward, it's an additional step that may not be necessary when using other evaluation methods.

Limited Representational Power: Postfix notation might not be the most natural representation for expressing certain types of mathematical or logical expressions, especially if the problem domain requires a more complex hierarchical structure.

Conclusion

To wrap up, understanding postfix notation and being able to implement postfix evaluation in C is a vital aspect of proficient programming. By mastering this technique, you can make your algorithms more efficient and your code cleaner. But this isn't the end of your learning journey. You can further sharpen your skills and expertise in programming with upGrad’s specialized courses, which are tailored to make you industry-ready. Happy programming!

FAQs

1. What is an example of postfix evaluation?

An example of postfix evaluation is evaluating the expression 56+3*, which corresponds to the infix expression (5+6)*3.

2. How does a postfix evaluation calculator work?

A postfix evaluation calculator reads and evaluates postfix expressions from left to right using a stack to hold the operands.

3. Can you provide an example of postfix evaluation in C using array?

Sure, in C, you can create a stack using an array and evaluate postfix expressions by scanning the expression from left to right, pushing operands to the stack, and performing operations as operators are encountered.

4. Where can I find postfix evaluation code for practice?

There are multiple online platforms like GitHub where you can find sample codes for postfix evaluation in C for practice.

5. Why use stack for evaluation of postfix expression?

A stack is used because of its LIFO (Last In First Out) property, which allows for the correct sequence of operations in postfix expression evaluation.