Infix to Postfix – For operators – Following the rules

View Github Repository Open presentation in a new window

AmaanC

See all presentation from AmaanC

Infix to Postfix – For operators – Following the rules

0 0

dsa-pres

A tool which shows you all the steps in converting an infix expression to postfix (Reverse Polish Notation)

On Github AmaanC / dsa-pres

Infix to Postfix

Prepared by Amaan Cheval / @AmaanC

When I was asked to make this

But then...

...when I realized I could add GIFs to the slides!

Anyway

You have a choice

Write the code live, or go through slides?

Slides it is.

What is postfix?

Definition: Postfix notation is a mathematical notation in which every operator follows all of its operands.

Examples:

Infix Postfix a+b ab+ a+b*c abc*+ a*b+c ab*c+

Terms used

Stack: A last-in-first-out (LIFO) data structure.

Operand: a-z || A-Z || 0-9

Operator: /, *, +, -

Rules for the algortihm

1. If the character is an operand, add it to the output string.

For operators

2. if c == '(': push it to the stack.
3. else if c == ')': pop and add to output till you find the '('
4. else if ( stackIsEmpty || topOfStack == '(' || higherPrecedence(c, topOfStack) ): pushToStack(c)
5. else: pop all from stack and add to output

Looks complicated. Really, though, it isn't.

Following the rules

Let's convert "a+b*c" to postfix using the rules.

We iterate over each character

Current character: 'a'

It is an operand, so we add it to the output string. Stack: [] Output string: 'a'

Current character: '+'

Stack is empty, so push it to stack. Stack: ['+'] Output string: 'a'

Current character: 'b'

Operand, so add it to the output string. Stack: ['+'] Output string: 'ab'

Current character: '*'

Operand has higher precedence than the top of the stack ('+'), so we push to stack. Stack: ['+', '*'] Output string: 'ab'

Current character: 'c'

Operand, so add it to the output string. Stack: ['+', '*'] Output string: 'abc'

Current character: '\0'

End of string, so pop the entire string and add it to the output string. Stack: [] Output string: 'abc*+'

I also built a tool to show steps.

Let's look at code!

First, some helper functions. 
int operand(char c) {
    // Returns 0 if c is an operator
    // Returns 1 if c is an operand (like a or c)
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}
A function that gives you the priority of an operator. 
int getValueForOperator(char op) {
    int val = 0;
    switch(op) {
        case '/':
            val = 4;
            break;
        case '*':
            val = 3;
            break;
        case '+':
            val = 2;
            break;
        case '-':
            val = 1;
            break;
        default:
            val = 0;
            break;
    }
    return val;
}
A function to let you compare operators for precedence. 
int higherPrecedence(char op1, char op2) {
    // Returns 1 if op1 has higher precedence. 0 otherwise
    int val1 = getValueForOperator(op1);
    int val2 = getValueForOperator(op2);
    return val1 > val2;
}
We can use it this way: 
if (higherPrecedence('+', '*')) {
	printf("+ is more important than *");
}

Real code!

We need to loop over every character in a string 
char exp[] = "a+b*c";
int i = 0;
char result[10];
int resultI = 0;

while (exp[i] != '\0') {
    c = exp[i];
    
    // We now have c, which is the current character.
    // All our code goes here, in the middle

    i++;
}

Rule 1

if (operand(c)) {
    result[resultI] = c;
    resultI++;
}

Rule 2

else {
    // It is an operator
    if (c == '(') {
        push(&s, c);
    }
    // We'll add more here, for the other rules
}

Rule 3

else {
    // It is an operator
    // Code for previous rules goes here
    else if (c == ')') {
        temp = pop(&s);
        while (temp != '(' && s.top >= 0) {
            result[resultI] = temp;
            resultI++;
            temp = pop(&s);
        }
    }
}

Rule 4

else {
    // It is an operator
    // Code for previous rules goes here
    else if (s.top < 0 || higherPrecedence(c, seeTop(&s)) || seeTop(&s) == '(') {
        push(&s, c);
    }
}

Rule 5

else {
    // It is an operator
    // Code for previous rules goes here
    else {
        // This means that the operator had a lower precedence than the top of the stack
        while (s.top >= 0) {
            temp = pop(&s);
            result[resultI] = temp;
            resultI++;
        }
    }
}

If there's anything left on the stack, after we're done with all the characters 

while (s.top >= 0) {
    temp = pop(&s);
    result[resultI] = temp;
    resultI++;
}

Links:

Shunting yard algorithmInfix to Postfix visualizerRepository: https://github.com/AmaanC/dsa-presThis presentation: http://whatthedude.com/dsa-pres/

And we're done!

Infix to Postfix Prepared by Amaan Cheval / @AmaanC