Infix to Postfix conversion

  Infix to Postfix conversion

================================================================================

  • Infix expression: The expression of the form a operator b (a + b). When an operator is in-between every pair of operands.
  • Postfix expression: The expression of the form a b operator (ab+). When an operator is followed by every pair of operands.
Infix to Postfix conversion



  • Algorithm:
    1. begin
    2. x = read first symbol from infix
    3. if ( x is '(' or ')' )
      1. if (x is '(' )
        1. push (x)
      2. end if
      3. if (x is ')' )
        1. pop() everything from stack and send to output till we get first '(' parenthesis but '(' not send to output
      4. end if
    4. end if
    5. if (x is operator)
      1. if (operator[TOP] < current (x) operator)
        1. push (x) i.e. push current operator on stack
      2. end if
      3. if (operator[TOP] > current (x) operator)
        1. pop(TOP operator) and send to output and push (current x) operator on the stack
      4. end if
      5. if (TOP == -1)
        1. push(x)
      6. end if
    6. end if
    7. x = read next symbol
    8. go to step 3
    9. print output string
    10. end

  • eg.

    • (A + B) * (C - D) / E

    • Solution:

    • Input

      Stack

      Output

      (



       

      A



      A

      +



       

      B



      A B

      )



      A B +

      *



      A B +

      (



      A B +

      C



      A B + C

      -



      A B + C

      D



      A B + C D

      )



      A B + C D -

      /



      A B + C D - *

      E



      A B + C D - * E

       

      A B + C D - * E /

Comments

Post a Comment

Popular posts from this blog

TREE

Image
TREE ================================================================================ A  Tree  is a  non-linear data structure  and a hierarchy consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”). A tree consists of a root, and zero or more subtrees T 1 , T 2 , … , T k  such that there is an edge from the root of the tree to the root of each subtree. Basic Terminologies:   Parent Node:  The node which is a predecessor of a node is called the parent node of that node.  {B}  is the parent node of  {D, E} . Child Node:  The node which is the immediate successor of a node is called the child node of that node. Examples:  {D, E}  are the child nodes of  {B}. Root Node:  The topmost node of a tree or the node which does not have any parent node is called the root node. {A }  is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other no
Read more

STACK

Image
STACK ================================================================================ Stack is a linear data structure that follows a particular order in which the operations are performed.  The order may be LIFO(Last In First Out) or FILO(First In Last Out). Basic Operation on Stack: push() :  To insert an element into the stack pop() :  To remove an element from the stack top() :  Returns the top element of the stack. isEmpty() :  Returns true if stack is empty else false. isFull() :  Returns true if stack is full else false. push(): Adds an item to the stack. If stack is full, then it said to be an "Overflow Condition". Time Complexity: 0(1) Only a new node is created and the pointer of the last node is updated. This includes only memory allocation operations. Hence it can be said that insertion is done in constant time. Algorithm: begin if stack is full return endif else increment top stack[top] = assign value end else end Flow Chart: %3CmxGraphModel%3E%3Croot%3E%3CmxCel
Read more

Evaluation of postfix expression

Image
    Evaluation of postfix expression ================================================================================  Postfix notation (also known as Reverse Polish Notation) is a way to represent an expression, where operators follow their corresponding operands.    Evaluating an expression represented as postfix notation can easily be done using the stack data structure. Algorithm: begin x = read first symbol from postfix expression while(x) if (x is an operator) operand1: pop() operand2: pop() result = operand2 operator operand1 push(result) end if else push(x) end else x = read next symbol end while end eg . 6 2 3 + - Solution:   Symbol Stack Evaluation 6   2   3   + operand1 = 3, operand2 = 2 result = 2 + 3 - operand1 = 5, operand2 = 6 result = 6 - 5  
Read more