Write a Program to Convert Expression from Infix to Postfix  using JavaScript in Compiler Design

This article presents a JavaScript program that converts infix expressions to postfix notation. We'll explore the theory behind infix and postfix notations, delve into the code implementation, and provide input/output examples.

Infix & Postfix Notation:

Infix notation is the traditional way of representing expressions, where operators are placed between operands. For example, the infix expression "(2 + 3)" denotes the addition of 2 and 3.

On the other hand, postfix notation, also known as Reverse Polish Notation (RPN), is an expression format where operators follow their respective operands. For the same addition operation, the postfix expression would be "2 3 +".

Converting an infix expression to postfix notation involves rearranging the operators based on their precedence and associativity rules. The process typically utilizes a stack to hold operators temporarily.

Convert Expression from Infix to Postfix in JavaScript:

Let's explore the JavaScript code that converts infix expressions to postfix notation:

function precedence(c) {
    if (c == '^') {
        return 3;
    }
    else if (c == '/' || c == '*') {
        return 2;
    }
    else if (c == '+' || c == '-') {
        return 1;
    }
    else {
        return 0;
    }
}

function isOperand(c) {
    if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) {
        return 1;
    }
    return 0;
}

function infixToPostfix(infix) {
    let stack = [];
    let postFix = "";

    for (let i = 0; i < infix.length; i++) {
        if (isOperand(infix[i])) {
            postFix += infix[i];
        }
        else if (infix[i] == '(') {
            stack.push('(');
        }
        else if (infix[i] == ')') {
            while (stack[stack.length - 1] != '(') {
                postFix += stack[stack.length - 1];
                stack.pop();
            }
            stack.pop();
        }
        else {
            while (stack.length != 0 && precedence(infix[i]) <= precedence(stack[stack.length - 1])) {
                postFix += stack[stack.length - 1];
                stack.pop();
            }
            stack.push(infix[i]);
        }
    }
    while (stack.length != 0) {
        postFix += stack[stack.length - 1];
        stack.pop();
    }
    return postFix;
}

let infix = "(A+B)*(c/d)+2";
console.log(`The given infix expression is: ${infix}`);
console.log(`The corresponding postfix expression is: ${infixToPostfix(infix)}`);

Input/Output: For the given infix expression "(A+B)*(c/d)+2", the program produces the following output:

The given infix expression is: (A+B)*(c/d)+2

The corresponding postfix expression is: AB+cd/+2+

Explanation:

Let's go through the code step by step to understand how it Converts Expression from Infix to Postfix :

The code begins by defining two helper functions: precedence and isOperand. 

The precedence function assigns precedence values to the operators, where higher values indicate higher precedence. The isOperand function checks whether a character is an operand, including letters and numbers.

The main function, infixToPostfix, takes an infix expression as input and iterates through each character. It performs different actions based on the type of character encountered. 

If an operand is found, it is appended to the postfix string. Opening parentheses are pushed onto the stack, and when a closing parenthesis is encountered, the operators inside the parentheses are popped from the stack and appended to the postfix string. 

Operators are pushed onto the stack after comparing their precedence with the top operator on the stack. Finally, any remaining operators on the stack are appended to the postfix string.

Conclusion: 

In this article, we have explored the conversion of infix expressions to postfix notation using JavaScript. We learned about the theory behind infix and postfix notations, and how to implement the conversion algorithm using a stack and precedence rules. 

Happy coding!

Next Article:

Write a Program to Convert Expression from Postfix to Infix  using JavaScript in Compiler Design

Previous Article:

Write a Program to Count The Number of Lexeme using JavaScript in Compiler Design

 

Ashraf Compiler Design