Our
topic about "Polish Notations" and we will see what is it, how to be used
in our projects and also it's importance.
We
usually write algebraic expressions like this: a + b
This
is called infix notation, because the operator (“+”)
is
inside the expression. A problem is that we need parentheses
or
precedence rules to handle more complicated expressions:
For
Example :
a +
b * c = (a + b) * c ?
= a + (b * c) ?
Q: Why would anyone ever want to use
anything so “unnatural,” when infix seems to work just fine?
A: With postfix and prefix notations,
parentheses are no longer needed!
Example
|
infix
|
postfix
|
prefix
|
|
(a
+ b) * c
|
a
b + c *
|
*
+ a b c
|
|
a
+ (b * c)
|
a
b c * +
|
+
a * b c
|
Infix
form :
<identifier> <operator> <identifier>
Postfix
form :
<identifier> <identifier> <operator>
Prefix
form :
<operator> <identifier> <identifier>
-> So what
is prefix, postfix and infix notations?
(1)
Polish notation,
also known as polish prefix notation or simply prefix notation, is a form of
notation for logic, arithmetic, and algebra invented by Polish
mathematician Jan Lukasiewicz in the 1920's. When using Polish notation, the
instruction (operation) precedes the data (operands). In Polish notation, the
order (and only the order) of operations and operands determines the result,
making parentheses unnecessary.
Or
simply is a way of expressing arithmetic expressions that avoids the use of
brackets to define priorities for evaluation of operators. In this
notation, the operators preceded their arguments, so that the expression
(3 + 5) * (7 - 2) would be written as * + 3 5 - 7 2
Notes: - In
Prefix notation, the operator comes before the operand.
- The Infix expression A+B will be
written as +AB in its Prefix Notation.
(2)
Infix notation
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. A
+ B
(3)
Postfix notation
In
Postfix notation, the operator comes after the Operand.
For
example, the Infix expression A+B will be written as AB+ in its Postfix
Notation.
Postfix
is also called ‘Reverse Polish Notation’
It
provided a straightforward solution for calculator or computer software
mathematics because it treats the instructions (operators) and the data
(operands) as "objects" and processes them in a last-in, first-out
(LIFO) basis. This is called a "stack method". (Think of a stack of
plates. The last plate you put on the stack will be the first plate taken off
the stack.)
so
that the InfixNotation expression (3 + 5) * (7 - 2)
would
be written as 3 5 + 7 2 - *
-> Now,
we will explain the conversion method between these types and will start with the
conversion process from infix to prefix as follow:
Conversion
from Infix Expression to Prefix
Let
we have an infix Expression ((a+b) * (c+d) / (e-f)) + g and want to convert it
to prefix.
Conversion
Steps:
- As shown in the table below, we have input, prefix_stack & stack columns.
- Reading
expression from “right to left” character by character as it shown in the input
column.
Now converting this expression to
prefix as it shown:
· We
started from the most right character in the expression (g).
· Because
‘g’ is operand it should be put in the prefix_stack and so on with each
operand character.
· When
converting the most second character (+), because it is operator it should be
put in the stack.
· If
the character is ‘)’ also we treat it as any other operator like the previous
‘+’ one.
· If
the character is ‘(‘ so it will be different becaue like this case in the stack
+))- and the current character in the input column is ‘(‘ so will handle it as
follow:
- remove ‘)-‘ from the stack so it will become ‘+)’
- Put ‘-‘ in the prefix_stack so if it was gfe it will become gfe-
-
Repeat the previous steps with all
remaining characters until we reach the end of expression, in our case it
will be Gfe-dc+ba+*/+, so to get the final result we will write the expression
from right to left one by one (or simply reverse) to get the final
result: +/*+ab+cd-efg
|
Input
|
prefix_stack
|
Stack
|
|
|
|
|
|
g
|
g
|
Empty
|
|
+
|
g
|
+
|
|
)
|
g
|
+)
|
|
)
|
g
|
+))
|
|
f
|
gf
|
+))
|
|
-
|
gf
|
+))-
|
|
e
|
gfe
|
+))-
|
|
(
|
gfe-
|
+)
|
|
/
|
gfe-
|
+)/
|
|
)
|
gfe-
|
+)/)
|
|
d
|
gfe-d
|
+)/)
|
|
+
|
gfe-d
|
+)/)+
|
|
c
|
gfe-dc
|
+)/)+
|
|
(
|
gfe-dc+
|
+)/
|
|
*
|
gfe-dc+
|
+)/*
|
|
)
|
gfe-dc+
|
+)/*)
|
|
b
|
gfe-dc+b
|
+)/*)
|
|
+
|
gfe-dc+b
|
+)/*)+
|
|
a
|
gfe-dc+ba
|
+)/*)+
|
|
(
|
gfe-dc+ba+
|
+)/*
|
|
(
|
gfe-dc+ba+*/
|
+
|
|
Empty
|
gfe-dc+ba+*/+
|
Empty
|
-> Evaluation
of infix expression ( and verification)
- To
make sure from the results just assign values to all operands like that
A=14,
b=12, c=10, d=8, e=6, f=4, e=2
- Then
evaluate infix expression using above values
((14+12)*(10+8)/(6-4))
+ 2
(26*18/2)
+2
(468/2)+2
(234)+2
à 236
Now
apply your new conversion result to make sure that the process executed well as
shown:
+/* +
14 12 +10 8 – 6 4 2 à (14+2&10+8 &6-4)
+/ *
26 18 2 2
à (26
*18 )
+ /
468 2 2
à (468/2)
+
234 2
à (234+2)
à 236
-
Both
are same, so our conversion is correct!
-> If
you are familiar with algorithms you can have a look at this conversion
algorithm.
Arr
= (infix Expression)
Set
Loop_counter to length_of_arr
Do
Character = arr[Loop_counter]
If character is operator
Push character to prefix_stack
If character is ‘)’
Do
Pop character and push it to prefix_stack
Untl character equals ‘(‘
If character is operator
If character_precedence is greater Or is equal to stack[top]_precedence
Push to stack
Else
Do
Push from stack and push it to prefix_stack
Until condition satisfies
Loop_counter = Loop_counter -1
While
Loop_counter is not equal to 0
Pop
out prefix_stack and display each element
The next part we will discuss the conversion process from infix to postfix expression.
To Be Continued..,
See you in the next parts.
No comments:
Post a Comment