Introduction: Infix,Postfix and Prefix expression

Infix Notation:

• In infix notation, operators are placed between their operands.
• This is the standard notation used in mathematics.
• Example:

Example: 2 x 3 + 4 
In this expression, the addition operator (+) is between the operands 2 and 3×4.

Postfix Notation (Reverse Polish Notation):

• In postfix notation, operators follow their operands.
• Postfix notation does not require parentheses or precedence rules, as the order of operations is implicit.

Example: 2 3 4 X +
This postfix expression is equivalent to the infix expression: 2+(3×4)

Prefix Notation (Polish Notation):

• In prefix notation, operators precede their operands.
• Like postfix notation, prefix notation does not require parentheses or precedence rules.

Example: +2×34

This prefix expression is equivalent to the infix expression: (2+(3×4))

Infix notation evaluation
2+3×4=2+(3×4)=2+12=14
Postfix notation evaluation
234×+=2+(3×4)=2+12=14
Prefix notation evaluation
+2×34=2+(3×4)=2+12=14

Need for Prefix and Postfix expression

Postfix and prefix expressions are alternative notations for arithmetic expressions, where the operators are placed after or before their operands, respectively. These notations offer several advantages in the context of data structures and expression evaluation:

• Ease of Parsing:

Postfix and prefix expressions are inherently easier to parse compared to infix expressions (traditional notation with operators between operands). There's no need to deal with operator precedence or parentheses because the order of operations is determined solely by the position of operators.

• Elimination of Parentheses:

Postfix and prefix expressions eliminate the need for parentheses to specify the order of operations. This simplifies both expression evaluation and parsing algorithms.

• Efficient Evaluation:

Postfix expressions can be efficiently evaluated using a stack-based algorithm known as the postfix evaluation algorithm (also called the reverse Polish notation (RPN) algorithm). This algorithm doesn't require any backtracking or parenthesis matching and evaluates expressions in a single pass.

Similarly, prefix expressions can be evaluated efficiently using a stack-based algorithm known as the prefix evaluation algorithm (also called the Polish notation algorithm).

• Reduction of Ambiguity:

Infix expressions can be ambiguous, especially when dealing with operator precedence and parentheses. Postfix and prefix expressions remove this ambiguity by explicitly stating the order of operations.

• Ease of Expression Manipulation:

Converting an infix expression to postfix or prefix notation (and vice versa) can be beneficial for expression manipulation, simplification, and optimization algorithms.

• Applications in Compiler Design and Parsing:

Postfix and prefix expressions are commonly used in compiler design, parsing algorithms, and expression trees. They simplify the process of parsing and evaluating arithmetic expressions in programming languages.

Need for Prefix and Postfix expression

Postfix and prefix expressions are alternative notations for arithmetic expressions, where the operators are placed after or before their operands, respectively. These notations offer several advantages in the context of data structures and expression evaluation:

• Ease of Parsing:

Postfix and prefix expressions are inherently easier to parse compared to infix expressions (traditional notation with operators between operands). There's no need to deal with operator precedence or parentheses because the order of operations is determined solely by the position of operators.

• Elimination of Parentheses:

Postfix and prefix expressions eliminate the need for parentheses to specify the order of operations. This simplifies both expression evaluation and parsing algorithms.

• Efficient Evaluation:

Postfix expressions can be efficiently evaluated using a stack-based algorithm known as the postfix evaluation algorithm (also called the reverse Polish notation (RPN) algorithm). This algorithm doesn't require any backtracking or parenthesis matching and evaluates expressions in a single pass.

Similarly, prefix expressions can be evaluated efficiently using a stack-based algorithm known as the prefix evaluation algorithm (also called the Polish notation algorithm).

• Reduction of Ambiguity:

Infix expressions can be ambiguous, especially when dealing with operator precedence and parentheses. Postfix and prefix expressions remove this ambiguity by explicitly stating the order of operations.

• Ease of Expression Manipulation:

Converting an infix expression to postfix or prefix notation (and vice versa) can be beneficial for expression manipulation, simplification, and optimization algorithms.

• Applications in Compiler Design and Parsing:

Postfix and prefix expressions are commonly used in compiler design, parsing algorithms, and expression trees. They simplify the process of parsing and evaluating arithmetic expressions in programming languages.

Algorithm to convert Infix To Postfix

Algorithm: Infix to Postfix Conversion

Data:
- stack: Stack data structure to store operators
- postfix: String to store the resulting postfix expression

Operations:
1. InfixToPostfix(infixExpression)

Algorithm:
Let X be an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y.
1. Push “(“ onto Stack, and add “)” to the end of X.
2. Scan X from left to right and repeat Steps 3 to 6 for each element of X until the Stack is empty.
3. If an operand is encountered, add it to Y.
4. If a left parenthesis is encountered, push it onto Stack.
5. If an operator is encountered, then:
   I. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than the operator.
   II. Add the operator to Stack.
6. If a right parenthesis is encountered, then:
   I. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.
   II. Remove the left parenthesis.
7. END.

Convert Infix Expression to postfix: A+ (B*C-(D/E^F)*G)*H, where ^ is an exponential operator.

Convert the following infix expression to its postfix form: : 

                                      A ^ B * C - C + D/A/(E + F)

Consider the following arithmetic infix expression P into postfix expression

P=A+(B/C-(D*E^F)+G)*H

Evaluation of Postfix Expression

Algorithm for Evaluation of Postfix Expression:

1. Create an empty stack.
2. Start scanning the postfix expression from left to right.
3. For each element in the expression:
    a. If the element is an operand, push it onto the stack.
    b. If the element is an operator O:
        i. Pop twice from the stack to get operands A and B.
        ii. Calculate the result of B O A.
        iii. Push the result back onto the stack.
4. When the expression is fully scanned:
    - The value remaining in the stack is the final answer.
5. END.

Evaluation of Postfix Expression

Evaluate postfix expression: 4 5 6 * 

Postfix Expression: 456*+

| Step |  Element  |   Stack   |       Action      |
|------|-----------|-----------|-------------------|
|   1  |     4     |     4     | Push 4 onto Stack |
|   2  |     5     |  4, 5     | Push 5 onto Stack |
|   3  |     6     | 4, 5, 6   | Push 6 onto Stack |
|   4  |     *     |  4, 30    | Pop operands 5 and 6, calculate 6 * 5 = 30, push result onto Stack |
|   5  |     +     |   34      | Pop operands 4 and 30, calculate 30 + 4 = 34, push result onto Stack |
|   6  |           |    34     | Final answer: 34 |

evaluate postfix expression: 2 10 + 9 6 - /

Postfix Expression: 2 10 + 9 6 - /

| Step |  Element  |   Stack   |       Action      |
|------|-----------|-----------|-------------------|
|   1  |     2     |     2     | Push 2 onto Stack |
|   2  |     10    |  2, 10    | Push 10 onto Stack |
|   3  |     +     |   12      | Pop operands 2 and 10, calculate 10 + 2 = 12, push result onto Stack |
|   4  |     9     |     9     | Push 9 onto Stack |
|   5  |     6     |  9, 6     | Push 6 onto Stack |
|   6  |     -     |    3      | Pop operands 9 and 6, calculate 9 - 6 = 3, push result onto Stack |
|   7  |     /     |    4      | Pop operands 12 and 3, calculate 12 / 3 = 4, push result onto Stack |
|   8  |           |     4     | Final answer: 4 |

Evaluate POSTFIX EXPRESSION: 5 3 + 8 2 - *

Postfix Expression: 5 3 + 8 2 - *

| Step |  Element  |   Stack   |       Action      |
|------|-----------|-----------|-------------------|
|   1  |     5     |     5     | Push 5 onto Stack |
|   2  |     3     |  5, 3     | Push 3 onto Stack |
|   3  |     +     |    8      | Pop operands 5 and 3, calculate 3 + 5 = 8, push result onto Stack |
|   4  |     8     |  8, 8     | Push 8 onto Stack |
|   5  |     2     | 8, 8, 2   | Push 2 onto Stack |
|   6  |     -     |   8, 6    | Pop operands 8 and 2, calculate 8 - 2 = 6, push result onto Stack |
|   7  |     *     |    48     | Pop operands 8 and 6, calculate 6 * 8 = 48, push result onto Stack |
|   8  |           |    48     | Final answer: 48 |

Infix to Prefix Conversion Using Stack

The following diagram shows steps to be followed to convert given infix expression to prefix expression:

Algorithm to convert given infix expression  to prefix expression:

Algorithm: Infix to Prefix Conversion

Data:
- stack: Stack data structure to store operators and parentheses
- prefix: String to store the resulting prefix expression

Operations:
1. InfixToPrefix(infixExpression)

Algorithm:

1. Reverse the infix expression.
2. Replace '(' with ')' and vice versa in the reversed expression.
3. InfixToPostfix(Reversed Expression)
6. Reverse the prefix expression to get the final prefix expression.
7. Return prefix.

convert the given Infix to prefix : (A+B^C)*D+E^5 

 Step 1. Reverse the infix expression. 

            5^E+D*)C^B+A(     

Step 2. Make Every '(' as ')' and every ')' as '(' 

             5^E+D*(C^B+A) 

Step 3. Convert expression to postfix form. 

A+(B*C-(D/E-F)*G)*H 

Step 4: reverse the expression  :  +*+A^BCD^E5 (Result) 

EVALUATION OF PREFIX EXPRESSION

Algorithm to evaluate prefix expression

Algorithm: Evaluation of Prefix Expression

Data:
- stack: Stack data structure to store operands
- result: Variable to store the final result of the expression

Operations:
1. EvaluatePrefix(prefixExpression)

Algorithm:

1. Put a pointer P at the end of the prefix expression.
2. While P is greater than or equal to 0:
    a. If the character at position P is an operand:
        i. Push it onto the stack.
    b. If the character at position P is an operator:
        i. Pop two elements from the stack.
        ii. Operate on these elements according to the operator.
        iii. Push the result back onto the stack.
    c. Decrement P by 1.
3. The result is stored at the top of the stack.
4. Return the result.
5. END.

Evaluate prefix expression: Expression: +9*26