# Infix, Postfix and Prefix Conversion

## What is Infix Notation

** Infix notation is a method of writing mathematical expressions that are commonly used in everyday calculations, as well as in computer programming languages**. In this notation, operators such as addition (+), subtraction (-), multiplication (*), and division (/) are written between the operands or the numbers on which the operations are performed.

**For example, **the expression **2 + 3** is written in infix notation as "2 plus 3", with the plus symbol between the two operands. Similarly, the expression 4 *5 is written as "4 times 5", with the multiplication symbol placed between the two operands.

Infix notation is widely used because it is intuitive and easy to read and understand for most people. It follows the same order of operations as traditional arithmetic, meaning multiplication and division are performed before addition and subtraction. This order can be overridden using parentheses to group operations, just as in traditional arithmetic.

**For example, **the expression **2 + 3 * 4** can be ambiguous if we don't use parentheses toindicate which operation should be performed first. In this case, it could meaneither "2 plus 3, then multiplied by 4" or "3 multiplied by 4, then added to 2". So, to remove ambiguity, we can write the expression as (**2 + 3) * 4 or 2 + (3 * 4),** depending on the desired order of operations.

In addition to the standard arithmetic operators, infix notation can also include other mathematical and logical symbols, such as exponents (^) and square roots (v), and logical operators, such as **AND (&&) and OR (||).** These symbols are placed between the operands, just like the arithmetic operators.

Infix notation is used in many programming languages, including popular ones like

**C++, Java, and Python**. However, in programming languages, infix notation may be limited to a smaller set of operators and symbols, depending on the language syntax and rules.

Infix notation can be converted to other notations, such as postfix (also known as reverse Polish notation) and prefix (also known as Polish notation), which are used in some programming languages and calculators. These notations have advantages in certain contexts, such as easier parsing by computers or more efficient use of memory in calculators.

In conclusion, infix notation is a widely used and intuitive method of writing mathematical expressions that include operators placed between the operands.

It follows the same order of operations as traditional arithmetic and can include a variety of mathematical and logical symbols. Infix notation is used in many programming languages and can be converted to other notations for specific purposes.

## What is Postfix notation

Postfix notation, also known as **reverse Polish notation (RPN),** is a mathematical expression method that places operators after the operands. In this notation, the expressions are written in a way that makes it easy for computers to evaluate them. Postfix notation was developed by the Polish mathematician **Jan Lukasiewicz **in the 1920s and has since been used in many programming languages and calculators.

In postfix spaces separate notation, operands, and operators, and the order of operations is determined by the position of the operators. For example, the expression 2 + 3 is written as "2 3 +" in postfix notation. In this expression, the operator "+" follows the two operands "2" and "3". Similarly, the expression 4 * 5 is written as "4 5 *",* *with the operator "* following the two operands.

The advantage of postfix notation is that it eliminates the need for parentheses and the order of operations becomes unambiguous. The expressions can be evaluated by a simple **stack-based algorithm,** which makes it easy to implement in programming languages and calculators.

To evaluate an expression in postfix notation, a stack data structure is used to keep track of the operands and operators. The operands are pushed onto the stack, and when an operator is encountered, the top two operands are popped from the stack, the operator is applied to them, and the result is pushed back onto the stack.

For example, to evaluate the postfix expression "2 3 + 4 *",* *we would start by pushing the operands 2 and 3 onto the stack. When we* *encounter the "+" operator, we pop 3 and 2 from the stack, add them* *together, and push the result, 5, back onto the stack. We then push the operand* *Four onto the stack. When we encounter the "* operator, we pop 4 and 5 from the stack, multiply them together, and push the result, 20, back onto the stack. The final result, 20, is the only value left on the stack.

Postfix notation can also include other operators and symbols, such as exponents (^) and square roots (v), and logical operators, such as AND (&&) and OR (||).

These symbols are placed after the operands, just like the arithmetic operators.

Postfix notation can be converted to infix notation or prefix notation, which can be useful for displaying expressions in a more human-readable format. However, the the conversion process can be complex, especially for expressions that include parentheses or nested operators.

Postfix notation is used in many programming languages, including **Forth, Factor, and the HP calculators**. It is also used in some computer architectures, where it can be used to simplify the design of hardware circuits for arithmetic and logical operations.

## What is Prefix notation

Prefix notation, also known as **Polish notation,** is a method of writing mathematical expressions in which operators are placed before their operands. This notation was invented by the Polish mathematician **Jan Lukasiewicz** in the 1920s and has since been used in many programming languages and calculators.

In prefix notation, the expressions are written in a way that makes it easy for computers to evaluate them. Spaces separate operators and operands, and the position of the operators determines the order of operations. For example, the expression 2 + 3 is written in prefix notation as "+ 2 3". *In this expression, the operator "+" comes before the two operands*

"2" and "3". Similarly, the expression 4 * 5 is written as "* 4 5", with the operator "*" preceding the two operands.

The advantage of prefix notation is that it eliminates the need for parentheses and the order of operations becomes unambiguous. The expressions can be evaluated by a simple** stack-based algorithm**, which makes it easy to implement in programming languages and calculators.

To evaluate an expression in prefix notation, a stack data structure is used to keep track of the operands and operators. The operators are pushed onto the stack, and when an operand is encountered, it is pushed onto the stack. When there are enough operands on the stack to satisfy an operator, the top operands are popped off the stack, the operator is applied to them, and the result is pushed back onto the stack.

For example, we would start by pushing the operator to evaluate the prefix expression "* + 2 3 4"." *onto the stack. When we encounter the "+" operator, we push it onto* *the stack, followed by operands 2 and 3. The next operator we encounter is* * *"*so we push it onto the stack, followed by the operand 4. We now have enough operands on the stack to satisfy the "*." operator, so we pop four and the result of "+" (which is 5) from the stack, multiply them together and push the result, 20, back onto the stack. The final result, 20, is the only value left on the stack.

Prefix notation can also include other operators and symbols, such as exponents (^) and square roots (v), and logical operators, such as AND (&&) and OR (||).

These symbols are placed before the operands, just like the arithmetic operators.

Prefix notation can be converted to infix notation or postfix notation, which can be useful for displaying expressions in a more human-readable format. However, the conversion process can be complex, especially for expressions that include parentheses or nested operators.

Prefix notation is used in many programming languages, including **Lisp, Scheme, and the early versions of the HP calculators.** It is also used in some computer architectures, where it can be used to simplify the design of hardware circuits for arithmetic and logical operations.

In conclusion, prefix notation is a method of writing mathematical expressions in which operators are placed before their operands. It eliminates the need for parentheses and makes the order of operations unambiguous. Prefix notation can be evaluated by a simple stack-based algorithm and is used in many programming languages and calculators. It can also include a variety of mathematical and logical symbols and can be converted to infix or postfix notation for display purposes.

## What is Infix to Postfix conversion?

Infix notation is a common way of writing mathematical expressions where the operators are placed between the operands, such as **2 + 3 or 4 * 5.** However, postfix notation (also known as reverse Polish notation) is another way of writing expressions where the operators come after the operands, such as **2 3 + or 4 5 *.** Converting infix notation to postfix notation can be useful in certain contexts, such as when implementing **calculators or compilers.**

- The conversion process involves scanning the infix expression from left to right and using a stack to keep track of the operators.
- When an operator is encountered, it is placed onto the stack.
- However, before placing the operator onto the stack, any operators of higher or equal precedence already on the stack must be popped off and appended to the postfix expression. This ensures that operators of higher precedence are evaluated first.
- When an opening parenthesis is encountered, it is placed onto the stack.
- When a closing parenthesis is encountered, all operators on the stack are popped off and appended to the postfix expression until the opening parenthesis is reached, which is then popped off and discarded.

### Steps for Infix to Postfix Conversion:

For example, Take the infix expression "**3 + 4 * 2 / (1 - 5 ) ^ 2 ^ 3**" as an example. To convert this expression to postfix notation, we follow these steps:

1. Create an empty stack and an empty postfix expression.

2. Scan the infix expression from left to right.

3. If the current character is an operand (in this case, a number), append it to the postfix expression.

4. If the current character is an operator (+, -, *, /, ^), then:

**a**. While there are operators of higher or equal precedence on the stack, pop them off and append them to the postfix expression.

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

5. If the current character is an opening parenthesis, push it onto the stack.

6. If the current character is a closing parenthesis, pop operators off the stack and append them to the postfix expression until the opening parenthesis is reached, which is then popped off and discarded.

7. After scanning the entire expression, pop any remaining operators off the stack and append them to the postfix expression.

Using the above steps, we can convert the infix expression "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" to postfix notation as follows:

1. Empty stack:

2. Process "3": Postfix expression: 3

3. Process "+": Stack: + Postfix expression: 3

4. Process "4": Postfix expression: 3 4

5. Process "*": Stack: * Postfix expression: 3 4

6. Process "2": Postfix expression: 3 4 2

7. Process "/": Stack: / Postfix expression: 3 4 2 *

8. Process "(": Stack: ( / Postfix expression: 3 4 2 *

9. Process "1": Postfix expression: 3 4 2 * 1

10. Process "-": Stack: - ( / Postfix expression: 3 4 2 * 1

11. Process "5": Postfix expression: 3 4 2 * 1 5

12. Process ")": Stack: / Postfix expression: 3 4 2 * 1 5 - ^

13. Process "^": Stack: ^ / Postfix expression: 3 4 2 * 1 5 - ^ ^

14. Process "2": Postfix expression: 3 4 2 * 1 5 - ^ ^ 2

15. Process "^": Stack: ^ ^ / Postfix expression: 3 4 2 * 1 5 - ^ ^ 2 ^

16. Final postfix expression: 3 4 2 * 1 5 - ^ ^ 2 ^ +

Therefore, the infix expression "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" can be converted to postfix notation as **"3 4 2 * 1 5 - ^ ^ 2 ^ +".**

## What is Infix to Prefix Conversion?

Infix-to-prefix conversion involves converting an infix expression to its prefix notation. This can be done using steps similar to the infix to postfix conversion, but with a few modifications. **The steps are as follows:**

1. Reverse the infix expression

2. Use the same algorithm as an infix to postfix conversion to obtain the postfix expression of the reversed infix expression

3. Reverse the postfix expression to obtain the prefix expression

Let's take the same example infix expression we used before: "**3 + 4 * 2 / (1 - 5 ) ^ 2 ^ 3".**

- Reverse the infix expression: "3 ^ 2 ^ (5 - 1) / 2 * 4 + 3"
- Use the infix to postfix conversion algorithm to obtain the postfix expression of the reversed infix expression: "3 4 2 * 1 5 - ^ ^ 2 / +"
- Reverse the postfix expression to obtain the prefix expression: "+ / ^ ^ 2 - 5 1 * 2 4 3."

Therefore, the infix expression "3 + 4 * 2 / (1 - 5) ^ 2 ^ 3" can be converted to prefix notation as **"+ / ^ ^ 2 - 5 1 * 2 4 3".**

## What is Postfix to Infix conversion?

Postfix to infix conversion converts an expression written in postfix notation to its equivalent infix notation. The operator is written after its operands in postfix notation, also known as Reverse Polish notation. On the other hand, infix notation is the conventional notation where the operator is written between the operands.

Here is an example of a postfix notation expression:

**6 3 2 - ***

To convert this expression to infix notation, we follow these steps:

**Step 1**: Start from the left and scan each element of the expression.

**Step 2**: If the current element is an operand, push it onto a stack.

**Step 3**: If the current element is an operator, pop two operands from the stack, place them on either side of the operator in infix notation, and enclose the entire expression in parentheses. Then push the resulting expression back onto the stack.

Applying these steps to our example:

- We start scanning the expression from the left. The first element is 6, an operand, so we push it onto the stack.

**Stack: 6**

- The next element is 3, also an operand, so we push it onto the stack.

**Stack: 6 3**

- The next element is 2, also an operand, so we push it onto the stack.

**Stack: 6 3 2**

- The next element is -, which is an operator. In that order, we pop the last two operands from the stack, which are 3 and 2. We place them on either side of the operator in infix notation, enclosed in parentheses. We get (3 - 2). We then push this resulting expression back onto the stack.

**Stack: 6 (3 - 2)**

- The next element is
***,**which is an operator. In that order, we pop the last two operands from the stack, which are 6 and (3 - 2). We place them on either side of the operator in infix notation, enclosed in parentheses. We get 6 * (3 - 2). We then push this resulting expression back onto the stack.

**Stack: (6 * (3 - 2))**

- We have reached the end of the expression, and the final result is the expression on the top of the stack, which is (6 * (3 - 2)). This is the equivalent infix notation of the original postfix expression
**6 3 2 - *.**

## What is Prefix-to-Infix conversion?

Prefix-to-infix conversion converts an expression written in prefix notation to its equivalent infix notation. The operator is written before its operands in prefix notation, also known as Polish notation. On the other hand, infix notation is the conventional notation where the operator is written between the operands.

Here is an example of a prefix notation expression:

*** - 6 3 2**

**To convert this expression to infix notation, we follow below steps:**

**Step 1:** Start from the right and scan each element of the expression.

**Step 2:** If the current element is an operand, push it onto a stack.

**Step 3**: If the current element is an operator, pop two operands from the stack, place them on either side of the operator in infix notation, and enclose the entire expression in parentheses. Then push the resulting expression back onto the stack.

Applying these steps to our example:

- We start scanning the expression from the right. The first element is 2, an operand, so we push it onto the stack.

**Stack: 2**

- The next element is 3, also an operand, so we push it onto the stack.

**Stack: 2 3**

- The next element is 6, also an operand, so we push it onto the stack.

**Stack: 2 3 6**

- The next element is -, which is an operator. In that order, we pop the last two operands from the stack, which are 3 and 6. We place them on either side of the operator in infix notation, enclosed in parentheses. We get (3 - 6). We then push this resulting expression back onto the stack.

**Stack: 2 (3 - 6)**

- The next element is *, which is an operator. In that order, we pop the last two operands from the stack, which are 2 and (3 - 6). We place them on either side of the operator in infix notation, enclosed in parentheses. We get 2 * (3 - 6). We then push this resulting expression back onto the stack.

**Stack: (2 * (3 - 6))**

- We have reached the end of the expression, and the final result is the expression on the top of the stack, which is (2 * (3 - 6)). This is the equivalent infix notation of the original prefix
**expression * - 6 3 2.**