Scribd Logo
Upload

Welcome to Scribd!

  • 1 views

    Lecture 17 Stack Polish Notations II

    Uploaded by

    abdulsammad1305

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lecture 17 Stack Polish Notations II

    Uploaded by

    abdulsammad1305
    1 views43 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    1 views43 pages

    Lecture 17 Stack Polish Notations II

    Uploaded by

    abdulsammad1305

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 43

    Dr.

    Muhammad Shuaib Qureshi


    Stack: Polish Notations-II
    Polish Notations
     Operator Precedence
    ▪ Following are the precedence of each operator from highest to
    lowest.
    Infix: A * (B + C) – D / E
    Algorithmic Steps for Infix to Postfix Postfix:

    1) Examine the next element in the input.


    2) If it is operand, output it.
    3) If it is opening parenthesis, push it on stack.
    4) If it is an operator, then
    i) If stack is empty, push operator on stack.
    ii) If the top of stack is opening parenthesis, push operator on stack
    iii) If it has higher priority than the top of stack, push operator on stack.
    iv) Else pop the operator from the stack and output it, push scanned
    character, and repeat step 4.
    5) If it is a closing parenthesis, pop operators from stack and output them until
    an opening parenthesis is encountered. pop and discard the opening
    parenthesis.
    6) If there is more input go to step-1
    7) If there is no more input, pop the remaining operators to output.
    Infix to Postfix

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

    ▪ stack: <empty>
    ▪ output: []
    Infix to Postfix
    ( (A+ B ) * ( C- E ) ) /( F + G) )

    ▪ stack: (
    ▪ output: []
    Infix to Postfix
    (A+B)*(C-E))/(F+G))

    ▪ stack: ( (
    ▪ output: []
    Infix to Postfix
    A+B)*(C-E))/(F+G))

    ▪ stack: ( ( (
    ▪ output: []
    Infix to Postfix
    +B)*(C-E))/(F+G))

    ▪ stack: ( ( (
    ▪ output: [A]
    Infix to Postfix
    B)*(C-E))/(F+G))

     stack: ( ( ( +
     output: [A]
    Infix to Postfix
    )*(C-E))/(F+G))

     stack: ( ( ( +
     output: [A B]
    Infix to Postfix
    *(C-E))/(F+G))

    ▪ stack: ( (
    ▪ output: [A B + ]
    Infix to Postfix
    (C-E))/(F+G))

     stack: ( ( *
     output: [A B + ]
    Infix to Postfix
    C-E))/(F+G))

     stack: ( ( * (
     output: [A B + ]
    Infix to Postfix
    -E))/(F+G))

     stack: ( ( * (
     output: [A B + C ]
    Infix to Postfix
    E))/(F+G))

     stack: ( ( * ( -
     output: [A B + C ]
    Infix to Postfix
    ))/(F+G))

     stack: ( ( * ( -
     output: [A B + C E ]
    Infix to Postfix
    )/(F+G))

     stack: ( ( *
     output: [A B + C E - ]
    Infix to Postfix
    /(F+G))

     stack: (
     output: [A B + C E - * ]
    Infix to Postfix
    (F+G))

    ▪ stack: ( /
    ▪ output: [A B + C E - * ]
    Infix to Postfix
    F+G))

     stack: ( / (
     output: [A B + C E - * ]
    Infix to Postfix
    +G))

     stack: ( / (
     output: [A B + C E - * F ]
    Infix to Postfix
    G))

     stack: ( / ( +
     output: [A B + C E - * F ]
    Infix to Postfix
    ))

    ▪ stack: ( / ( +
    ▪ output: [A B + C E - * F G ]
    Infix to Postfix
    )

    ▪ stack: ( /
    ▪ output: [A B + C E - * F G + ]
    Infix to Postfix

     stack: <empty>
     output: [A B + C E - * F G + / ]
    ❖ Infix to Postfix Example
    ❖ Infix String: ( a + b ) * ( c + d )

    Scanned Character Content of Stack Postfix String


    Empty Empty Empty
    Infix to Postfix Example
    ❖ Infix String: ( a + b ) * ( c + d )

    Scanned Character Content of Stack Postfix String


    Empty Empty Empty
    ( ( Empty
    a ( a
    + (+ a
    b (+ ab
    ) Empty ab+
    * * ab+
    ( *( ab+
    c *( ab+c
    + *(+ ab+c
    d *(+ ab+cd
    ) * ab+cd+
    Empty ab+cd+*
    Infix to Postfix Example
    ❖ Infix String: ( A * B - ( C + D ) + E )

    Scanned Character Content of Stack Postfix String


    Empty Empty Empty
    A Empty A
    * * A
    B * AB
    - - AB *
    ( -( AB *
    C -( AB * C
    + -(+ AB * C
    D -(+ AB * CD
    ) - AB * CD +
    + + AB * CD + -
    E + AB * CD + - E
    Empty AB * CD + - E +
    Infix to Postfix Example
    ❖ Infix String: ( A + B * C – D / E * H)

    Scanned Character Content of Stack Postfix String

    Empty Empty Empty


    A Empty A
    + + A
    B + AB
    * +* AB
    C +* ABC
    - - ABC*+
    D - ABC*+D
    / -/ ABC*+D
    E -/ ABC*+DE
    * -* ABC*+DE/
    H -* ABC*+DE/H
    ABC*+DE/H*-
    Empty
    Activity: Infix to Postfix
    i. A/( B-C)* D + E
    ii. M + N * P – Q /R*S
    iii. A – (B + C * D) / E
    Evaluation of Postfix Expressions
    Evaluation of postfix expressions (Without Stack)

    1. Scan the expression from left to right.

    2. Each time an operator is encountered, apply it to the


    two operands that immediately before the operator.

    3. Replace the operands and the operator with the result.

    4. Continue scanning the expression to the right.


    Example: postfix expressions Evaluation (without Stack)

    Rules

    i. Scan the expression from left to right.


    ii. Each time an operator is encountered, apply it to the two operands that
    immediately before the operator.
    iii.Replace the operands and the operator with the result.
    iv. Continue scanning the expression to the right.
    Algorithm to evaluate postfix expressions (with Stack)

    1. Initialize an empty stack.


    2. For each element in postfix expression, do
    i. If operand is encountered, push it on stack
    ii. else If operator is encountered, pop two elements
    A → top element
    B → Next to top element
    iii. result = B operator A
    Push result onto stack
    3. return element of stack top
    Evaluate postfix expressions
    Evaluating Postfix Expression
    ▪ Example: Consider the postfix expression, 2 10 + 9 6 - /, which is (2 + 10)
    / (9 - 6) in infix, the result of which is 12 / 3 = 4.

    ▪ The following is a trace of the postfix evaluation algorithm for the postfix
    expression:
    Evaluating postfix expressions (Using Open Stack)
    Evaluating postfix expressions (Using Open Stack)
    Infix to Prefix Conversion
    Polish Notations
    ▪ The way to write arithmetic expression is known as polish notation
    ▪ There are basically three types of polish notation:
    √ Infix: When the operator is written between two operands then it
    is known as Infix notation.
    ❖ For example, A+B
    √ Postfix: When the operator is written after their operands then it
    is known as Postfix notation.
    ❖ For example, AB+
    √ Prefix: When the operator is written before their operands then it
    is known as Prefix notation.
    ❖ For example, +AB
    Infix to prefix conversion
    ▪ Expression = (A+B) * C – D + F

    ✓ Step 1. Reverse the infix expression.


    F+D–C*)B+A(
    ✓ Step 2. Make Every '(' as ')' and every ')' as '(‘
    F+D–C*(B+A)
    ✓ Step 3. Convert expression to postfix form.
    FD + CBA + * -
    ✓ Step 4. Reverse the expression.
    - * + ABC+DF
    ▪ Result:
    Quiz
    (Next Class)

    You might also like