Polish Notation
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Polish Notation as PDF for free.
More details
- Words: 607
- Pages: 10
THE POLISH NOTATION
Arithmetic and Logical Expressions repeatedly scan through the expression ! take parentheses and priorities of operators into account
!
a + b + c * d - e / g a + b + ( c * d ) - ( e / g ) a + (( b + c ) * d - e ) / g a + b <= c && a + b <= d ( a + b <= c ) || ( a + b <= d )
S. Prasitjutrakul 1994
The Polish Notations Q : How can a compiler accept an expression and produce correct code ? A : Tranforming the expression into a form called Polish notation Infix form a * b a + b * c (a + b) * c
Prefix form * a b + a * b c * + a b c
Postfix form a b * a b c * + a b + c * Reverse Polish notation S. Prasitjutrakul 1994
Expression Evaluations : Stacks 5 * ( ( ( 9 + 8 ) + ( 4 * 6 ) ) - 7 ) Postfix form : 5 9 8 + 4 6 * + 7 - * Push( Push( Push( Push( Push( Push( Push( Push( Push( Push( Push(
5 ) 9 ) 8 ) Pop() 4 ) 6 ) Pop() Pop() 7 ) Pop() Pop()
+ Pop() )
* Pop() ) + Pop() ) - Pop() ) * Pop() ) S. Prasitjutrakul 1994
Expression Evaluations : Stacks 5 * ( ( ( 9 + 8 ) + ( 4 * 6 ) ) - 7 ) Postfix form : 5 9 8 + 4 6 * + 7 - *
5
9 5
6 4 17 5
24 17 5
8 9 5
17 5
4 17 5
41 5
7 41 5
34 5
170
S. Prasitjutrakul 1994
Infix Form → Postfix Form A / B ? C + D * E - A * C ( ( ( A / ( B ? C ) ) + ( D * E ) ) - ( A * C ) )
A B C ? /
D E * + A C * -
S. Prasitjutrakul 1994
Infix Form → Postfix Form A + B * C
A + B * C
A
+ A
+ A B
* + A B
A + B * C
A + B * C
A + B * C
* + A B C
+ A B C *
A B C * +
A + B * C
A + B * C
S. Prasitjutrakul 1994
Infix Form → Postfix Form (A+B)*C
(A+B)*C
(A+B)*C
(
( A
+ ( A
+ ( A B
(A+B)*C
(A+B)*C
(A+B)*C
(A+B)*C
A B +
* A B +
* A B + C
A B + C *
(A+B)*C
S. Prasitjutrakul 1994
Infix Form → Postfix Form X-(A+B)*C
X-(A+B)*C
X
X
( X
( X A
+ ( X A
X-(A+B)*C
X-(A+B)*C
X-(A+B)*C
X-(A+B)*C
X-(A+B)*C
X A B +
* X A B +
* X A B + C
X-(A+B)*C
+ ( X A B
X-(A+B)*C
X-(A+B)*C
X A B + C * -
S. Prasitjutrakul 1994
Operator Priorities Symbol ) ? *, / +, (
In-Stack Priority
In-Coming Priority
-
3
2 1 0
4 2 1 4
Operators are taken out of the stack as long as the in-stack priority is greater than or equal to the in-coming priority of the new operator.
? *
input : a*b?2 + 3 output: ab2 : ab2?∗ S. Prasitjutrakul 1994
Arithmetic and Logical Expressions repeatedly scan through the expression ! take parentheses and priorities of operators into account
!
a + b + c * d - e / g a + b + ( c * d ) - ( e / g ) a + (( b + c ) * d - e ) / g a + b <= c && a + b <= d ( a + b <= c ) || ( a + b <= d )
S. Prasitjutrakul 1994
The Polish Notations Q : How can a compiler accept an expression and produce correct code ? A : Tranforming the expression into a form called Polish notation Infix form a * b a + b * c (a + b) * c
Prefix form * a b + a * b c * + a b c
Postfix form a b * a b c * + a b + c * Reverse Polish notation S. Prasitjutrakul 1994
Expression Evaluations : Stacks 5 * ( ( ( 9 + 8 ) + ( 4 * 6 ) ) - 7 ) Postfix form : 5 9 8 + 4 6 * + 7 - * Push( Push( Push( Push( Push( Push( Push( Push( Push( Push( Push(
5 ) 9 ) 8 ) Pop() 4 ) 6 ) Pop() Pop() 7 ) Pop() Pop()
+ Pop() )
* Pop() ) + Pop() ) - Pop() ) * Pop() ) S. Prasitjutrakul 1994
Expression Evaluations : Stacks 5 * ( ( ( 9 + 8 ) + ( 4 * 6 ) ) - 7 ) Postfix form : 5 9 8 + 4 6 * + 7 - *
5
9 5
6 4 17 5
24 17 5
8 9 5
17 5
4 17 5
41 5
7 41 5
34 5
170
S. Prasitjutrakul 1994
Infix Form → Postfix Form A / B ? C + D * E - A * C ( ( ( A / ( B ? C ) ) + ( D * E ) ) - ( A * C ) )
A B C ? /
D E * + A C * -
S. Prasitjutrakul 1994
Infix Form → Postfix Form A + B * C
A + B * C
A
+ A
+ A B
* + A B
A + B * C
A + B * C
A + B * C
* + A B C
+ A B C *
A B C * +
A + B * C
A + B * C
S. Prasitjutrakul 1994
Infix Form → Postfix Form (A+B)*C
(A+B)*C
(A+B)*C
(
( A
+ ( A
+ ( A B
(A+B)*C
(A+B)*C
(A+B)*C
(A+B)*C
A B +
* A B +
* A B + C
A B + C *
(A+B)*C
S. Prasitjutrakul 1994
Infix Form → Postfix Form X-(A+B)*C
X-(A+B)*C
X
X
( X
( X A
+ ( X A
X-(A+B)*C
X-(A+B)*C
X-(A+B)*C
X-(A+B)*C
X-(A+B)*C
X A B +
* X A B +
* X A B + C
X-(A+B)*C
+ ( X A B
X-(A+B)*C
X-(A+B)*C
X A B + C * -
S. Prasitjutrakul 1994
Operator Priorities Symbol ) ? *, / +, (
In-Stack Priority
In-Coming Priority
-
3
2 1 0
4 2 1 4
Operators are taken out of the stack as long as the in-stack priority is greater than or equal to the in-coming priority of the new operator.
? *
input : a*b?2 + 3 output: ab2 : ab2?∗ S. Prasitjutrakul 1994
Related Documents
Polish Notation
June 2020 5
Notation
July 2020 20
Notation
November 2019 31
Notation
November 2019 32
Polish Grammar
April 2020 8