Skip to main content

Infix to postfix conversion


# Infix Expression Stack Postfix

Infix notation is the common way we write mathematical expressions, such as "2 + 3 * 4". However, it can be ambiguous and difficult for computers to evaluate. Postfix notation, also known as Reverse Polish Notation (RPN), is a way of writing mathematical expressions that avoids these problems.

In postfix notation, the operators follow the operands. For example, the expression "2 + 3 * 4" in postfix notation would be written as "2 3 4 * +". To convert an infix expression to postfix notation, we can use a stack to keep track of operators and their precedence.

Here are the steps to convert an infix expression to postfix notation:

  1. Create an empty stack and an empty output queue.

  2. Scan the infix expression from left to right.

  3. If the current token is an operand (a number), append it to the output queue.

  4. If the current token is a left parenthesis, push it onto the stack.

  5. If the current token is a right parenthesis, pop operators off the stack and append them to the output queue until a left parenthesis is found. Discard the left parenthesis.

  6. If the current token is an operator, then:

    a. While there is an operator at the top of the stack with greater or equal precedence, pop it off the stack and append it to the output queue.

    b. Push the current operator onto the stack.

  7. After the input expression has been completely scanned, pop any remaining operators off the stack and append them to the output queue.

  8. The postfix expression is the contents of the output queue, in order.

Let's illustrate this with an example. Consider the infix expression "2 + 3 * 4":

  1. Empty stack: [] Empty output queue: []

  2. Token "2": Output queue: [2]

  3. Token "+": Stack: [+] Output queue: [2]

  4. Token "3": Output queue: [2, 3]

  5. Token "": Stack: [] Output queue: [2, 3]

  6. Token "4": Output queue: [2, 3, 4]

  7. End of input: Pop remaining operator(s) off stack and append to output queue. Stack: [*] Output queue: [2, 3, 4, *]

  8. Postfix expression: "2 3 4 * +"

Therefore, the postfix notation of the given infix expression is "2 3 4 * +".

Here given code implementation process.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment