Polish Notation and Recursive Functions

Polish Notation

• Infix, Prefix, and Postfix are three types of Polish Notation
• Polish Notation is a process of writing operators before or after operands in an expression

Recursive Functions

• Recursion is a problem-solving approach where a problem is solved by repeatedly applying the same solution to smaller instances
• Recursive function is a programming technique that allows expressing operations in terms of themselves
• Examples of recursive functions:
  • Factorial of a number: Factorial(n) = 1 if n = 0, n * factorial(n-1) if n > 0
  • Fibonacci series: fibo(n) = 0 if n = 0 or n = 1, fibo(n) = fibo(n-1) + fibo(n-2) if n > 1
  • Greatest Common Divisor (GCD): gcd(a, b) = gcd(a-b, b) if a > b, gcd(a, b-a) if a < b, a or b if a = b

Converting Infix to Postfix Expression

• Steps to convert infix expression to postfix expression using stack:
  • Print operands as they arrive
  • If stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack
  • If incoming symbol is ‘(‘, push it onto stack
  • If incoming symbol is ‘)’, pop the stack and print operators until left parenthesis is found
  • If incoming symbol has higher precedence than the top of the stack
  • If incoming symbol has lower precedence than the top of the stack, pop and print the top
  • If expression ends, pop and print all operators of stack

Queue Data Structure

• A queue is a linear list of elements with deletion at one end (front) and insertion at the other end (rear)
• Also called First-in-First-out (FIFO) lists
• Real-life examples of Queue: row of students at a registration center, movie ticket window, line of cars waiting at a traffic signal
• Two ways to implement a queue: circular queue using array, linked structures (pointers)
• Primary queue operations: Enqueue (insert an element at the rear), Dequeue (remove an element from the front)

Circular Queue

• A circular queue is a type of queue data structure
• Algorithm for POP operation:
  • Check for stack underflow
  • Delete an element from the top of the stack
  • Decrement pointer
  • Return deleted element

Applications of Stack

• Three main applications of stack: recursion, stack machines, Polish notation
• Stack machine provides faster execution of Polish notation
• Better used for stacking local machines
• Used for representation of arithmetic expression