We studied theories back in school & college without knowing the practical applications of those theories. Stack in computer science was taught to us it follows a very simple logic called LIFO.
that is the last item in the collection can be removed first. The question is where is the application of this logic is used?. We use infix notation for representing mathematical operations or for manually performing calculations, since it is easier to read and comprehend. But for computers to perform quick calculations, they must work on prefix or postfix expressions.
So here going back to learn the fundamentals.
Calculators employing reverse Polish notation(Postfix notation) use a stack structure to hold values. Expressions can be represented in prefix,postfix or infix notations and conversion from one form to another may be accomplished using a stack.
Prefix notation is invented by a Polish logician & Philosopher hence it's also called Polish notation. In postfix notation Operators are written after their operands. it's called Reverse Polish Notation
Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code.Most programming languages are context-free languages, allowing them to be parsed with stack based machines.
Use Of Postfix Notation In Computer Science>
Because of the existence of this unique interpretation, some compilers first convert arithmetic expressions from the standard infix notation to postfix to simplify code generation. To convert an infix expression to postfix, we must use a stack to hold operators that cannot be processed until their operands are available.
A useful feature of postfix is that the order in which operators are applied is always unambiguous. That is, there is only a single interpretation of any postfix expression. This is not true of infix. For example, the meaning of the infix expression a + b * c is unclear. Does it mean (a + b) * c or a + (b * c)?Without parentheses or additional rules, we cannot say. In Java, precedence rules dictate that multiplication is performed before addition; we say that multiplication “takes precedence” over addition. The corresponding postfix expression is a b c * +, and there is no ambiguity. It is explicit that the multiplication operator applies to the immediately two preceding operands b and c. The addition operator is then applied to operand a and the result (b * c). If we had meant the expression (a + b) * c, we would have written it in postfix notation as a b + c *. Now the + operation is applied to the two operands a and b, and * is performed on the two operands c and the result (a + b).
Rules for Infix to Postfix>
Infix to Postfix Conversion Rules:>
1. We use a stack
2. When an operand is read, output it
3. When an operator is read
Operators are pushed in the precedence order to stack. i.e if the scanned operator has higher precedence than the top element in the stack, push it to stack. Else if the scanned operator is of lower precedence/same precedence than in the stack then pop the elements in the stack until the top of the stack element has lower precedence when compared to scanned operator. Then push the scanned operator.
step 3 in other words:
• When an operator is read
– Pop until the top of the stack has an element of lower precedence
– Then push it
4. When ) is found, pop until we find the matching (
5. When we reach the end of input, pop until the stack is empty.
Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 2). It is not as simple to parse by computers as prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ), but many programming languages use it due to its familiarity.
Example: A * B + C / D
Postfix notation (also known as "Reverse Polish notation"): Operators are written after their operands.
Example:
Prefix notation (also known as "Polish notation"): Operators are written before their operands.
Example:
Convert a prefix expression: A+(B*C)-D to postfix
Input Stack Output
-----------------------------------------------
In step 7 pop stack up to (
In step 8 pop items in stack up to when top stack element precedence is lower than -.
In step 10 when the input is empty pop all the remaining elements in the stack.
The advantage of converting prefix to postfix:>
1. The need for parantheses is eliminated.
2. The precedence rule is no longer relevant.
3. Evaluation can be achieved with great efficiency.
Priorities is BODMAS i.e
B - Brackets first.
O - Orders (ie Powers and Square Roots, etc.)
DM - Division and Multiplication (left-to-right)
AS - Addition and Subtraction (left-to-right)
i.e for example:
1. ^
2. * /
3. + –
Complex example for converting infix to postfix
Infix> (B^2 – 4 * A * C )^(1/2)
postfix> B2^4A*C*–12/^
Infix> 4 * (2 – (6 * 3 + 4) * 2) + 1
postfix> 4623*4+2*-*1+
1st rule in Converting infix to postfix using stack is:>
1. Begin to Read expression from Left-to-Right.
1st rule in Converting prefix to postfix using stack is:>
1. Begin to Read expression from Right-to-Left.
Rules For Converting Infix to prefix:>
1. Create 2 stacks: 1. OperatorStack & 2. Operand Stack
2. When an operand is read push it to OperandStack.
3. When an operator is read
Operators are pushed in the precedence order to stack. i.e if the scanned operator has higher precedence than the top element in the stack, push it to stack. Else if the scanned operator is of lower precedence/same precedence than in the stack then pop the elements in the stack until the top of the stack element has lower precedence when compared to scanned operator. Then push the scanned operator.
step 3 in other words:
• When an operator is read
– Pop until the top of the stack has an element of lower precedence
– Then push it
Note>poped item should go to Operand Stack.
4. When ( is found, pop until we find the matching )
5. When we reach the end of the input, pop until the operator stack is empty.
Only difference b/w PreFix & PostFix conversion from Infix is that reading the expression starts from right in prefix where as it's from left in postfix.
Infix to prefix example>
Infix: 4*(2-(6*3+4)*2)+1
Input OperatorStack OperandStack
--------------------------------------------------------------------
that is the last item in the collection can be removed first. The question is where is the application of this logic is used?. We use infix notation for representing mathematical operations or for manually performing calculations, since it is easier to read and comprehend. But for computers to perform quick calculations, they must work on prefix or postfix expressions.
So here going back to learn the fundamentals.
Calculators employing reverse Polish notation(Postfix notation) use a stack structure to hold values. Expressions can be represented in prefix,postfix or infix notations and conversion from one form to another may be accomplished using a stack.
Prefix notation is invented by a Polish logician & Philosopher hence it's also called Polish notation. In postfix notation Operators are written after their operands. it's called Reverse Polish Notation
Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code.Most programming languages are context-free languages, allowing them to be parsed with stack based machines.
Use Of Postfix Notation In Computer Science>
Because of the existence of this unique interpretation, some compilers first convert arithmetic expressions from the standard infix notation to postfix to simplify code generation. To convert an infix expression to postfix, we must use a stack to hold operators that cannot be processed until their operands are available.
A useful feature of postfix is that the order in which operators are applied is always unambiguous. That is, there is only a single interpretation of any postfix expression. This is not true of infix. For example, the meaning of the infix expression a + b * c is unclear. Does it mean (a + b) * c or a + (b * c)?Without parentheses or additional rules, we cannot say. In Java, precedence rules dictate that multiplication is performed before addition; we say that multiplication “takes precedence” over addition. The corresponding postfix expression is a b c * +, and there is no ambiguity. It is explicit that the multiplication operator applies to the immediately two preceding operands b and c. The addition operator is then applied to operand a and the result (b * c). If we had meant the expression (a + b) * c, we would have written it in postfix notation as a b + c *. Now the + operation is applied to the two operands a and b, and * is performed on the two operands c and the result (a + b).
Rules for Infix to Postfix>
Infix to Postfix Conversion Rules:>
1. We use a stack
2. When an operand is read, output it
3. When an operator is read
Operators are pushed in the precedence order to stack. i.e if the scanned operator has higher precedence than the top element in the stack, push it to stack. Else if the scanned operator is of lower precedence/same precedence than in the stack then pop the elements in the stack until the top of the stack element has lower precedence when compared to scanned operator. Then push the scanned operator.
step 3 in other words:
• When an operator is read
– Pop until the top of the stack has an element of lower precedence
– Then push it
4. When ) is found, pop until we find the matching (
5. When we reach the end of input, pop until the stack is empty.
Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 2). It is not as simple to parse by computers as prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ), but many programming languages use it due to its familiarity.
Example: A * B + C / D
Postfix notation (also known as "Reverse Polish notation"): Operators are written after their operands.
Example:
A B C + * D / Prefix notation (also known as "Polish notation"): Operators are written before their operands.
Example:
/ * A + B C D Convert a prefix expression: A+(B*C)-D to postfix
Input Stack Output
-----------------------------------------------
- A Empty A
- + + A
- ( (+ A
- B (+ AB
- * *(+ AB
- C *(+ ABC
- ) + A BC*
- - - ABC*+
- D - ABC*+D
- Empty ABC*+D-
In step 7 pop stack up to (
In step 8 pop items in stack up to when top stack element precedence is lower than -.
In step 10 when the input is empty pop all the remaining elements in the stack.
The advantage of converting prefix to postfix:>
1. The need for parantheses is eliminated.
2. The precedence rule is no longer relevant.
3. Evaluation can be achieved with great efficiency.
Priorities is BODMAS i.e
B - Brackets first.
O - Orders (ie Powers and Square Roots, etc.)
DM - Division and Multiplication (left-to-right)
AS - Addition and Subtraction (left-to-right)
i.e for example:
1. ^
2. * /
3. + –
Complex example for converting infix to postfix
Infix> (B^2 – 4 * A * C )^(1/2)
postfix> B2^4A*C*–12/^
Infix> 4 * (2 – (6 * 3 + 4) * 2) + 1
postfix> 4623*4+2*-*1+
1st rule in Converting infix to postfix using stack is:>
1. Begin to Read expression from Left-to-Right.
1st rule in Converting prefix to postfix using stack is:>
1. Begin to Read expression from Right-to-Left.
Rules For Converting Infix to prefix:>
1. Create 2 stacks: 1. OperatorStack & 2. Operand Stack
2. When an operand is read push it to OperandStack.
3. When an operator is read
Operators are pushed in the precedence order to stack. i.e if the scanned operator has higher precedence than the top element in the stack, push it to stack. Else if the scanned operator is of lower precedence/same precedence than in the stack then pop the elements in the stack until the top of the stack element has lower precedence when compared to scanned operator. Then push the scanned operator.
step 3 in other words:
• When an operator is read
– Pop until the top of the stack has an element of lower precedence
– Then push it
Note>poped item should go to Operand Stack.
4. When ( is found, pop until we find the matching )
5. When we reach the end of the input, pop until the operator stack is empty.
Only difference b/w PreFix & PostFix conversion from Infix is that reading the expression starts from right in prefix where as it's from left in postfix.
Infix to prefix example>
Infix: 4*(2-(6*3+4)*2)+1
Input OperatorStack OperandStack
--------------------------------------------------------------------
- 1 Empty 1
- + + 1
- ) )+ 1
- 2 )+ 21
- * *)+ 21
- ) )*)+ 21
- 4 )*)+ 421
- + +)*)+ 421
- 3 +)*)+ 3421
- * *+)*)+ 3421
- 6 *+)*)+ 63421
- ( +)*)+ *63421
- *)+ +*63421
- - -)+ *+*63421
- 2 -)+ *+*63421
- ( + -*+*63421
- * *+ -*+*63421
- 4 *+ 4-*+*63421
- Empty + *4-*+*63421
- Empty Empty +*4-*+*63421
Prefix:> +*4-*+*63421
Tips To Avoid Mistakes:>
1. Write down the previous operandStack first each time before scanning the symbol.
2. Then add the current input symbol if the scanned item is an operand.
2. Then add the current popped item one by one to the operand stack.
0 comments:
Post a Comment