49. Stack-2: (Prefix/Infix/Postfix)

# Note-

These are just different notations to write logical expressions.

Infix- (operator is b/w operands + human friendly + need brackets )
Prefix- (operator comes before operands + evaluate right to left)
Postfix- (operator comes after operands + evaluate left to right )

Priority order of operators:       (^)    >    ( *, / )    >    (+, -)
Prefix & postfix notation, do not require machines to have precedence rules.
------------------------------------------------------
# Learn, Infix to Postfix conversion (c1, say)
2. Infix to Prefix is modified c1
--------
# For other conversions (2.1, 2.2, 3.1, 3.2) traverse from the side, where operands come before operator⭐
---------------------------------------------------------------------------------------------------------------

1.1 Infix to Postfix-⭐

we can return numbers for each operator, and then compare the precedance.

Model-
Operators wait in stack till both operands are ready
-----------------------

----------------------------------------------------------------------------------------------------------------------------

1.2 Infix to Prefix-

1. reverse the given string & invert all brackets
2. do infix to postfix conversion
3. reverse the answer
---------------------------

---------------------------------------------------------------------------------------------------------------------------

2.1 Postfix to Infix-
(expression building)

1. iterate from left to right
2. if element is operand => push into stack
3. if it is an operator => pick last 2 elements from stack & push: (top1 # top2)
-----------
- when iteration is over, stack only contains 1 element (final infix expression) which is our answer
- this time we need a stack of string data type

-----------------------------------------------------------------------------------------------------------------------------

2.2 Prefix to Infix-

iterate from right to left (since operands on right in prefix)
else, exactly same logic as of 2.1

-----------------------------------------------------------------------------------------------------------------------------

3.1 Postfix to Prefix-

iterate from left to right (since we have operands on left in postfix)
1. if element is operand, push it into stack
2. if u see an operator, pop out last 2 operands from stack & push: ( # top2 top1 ) 

----------------------------------------------------------------------------------------------------------------------------

3.2 Prefix to Postfix-

1. iterate from right to left (since right side in prefix has operands)
2. if element = operand, push into stack
3. else, pop out last 2 top operands from stack & push: ( top1 top2 # )

---------------------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

36. Graphs-2 (traversal problems)

Image
1. No. of provinces Count total components in a graph, using any traversal technique ----------------------------------------------------------------------------------------------------------------------------- 2. Rotten oranges⭐     Multi source BFS time: O(n*m)   space: O(n*m) -------------- - count all fresh at start and then count if these many will rot in the process or not - here we do not need a visited matrix since we can modify given - we update time each time there rots atleast one orange in a BFS cycle --------------------------------------------------------------------------------------------------------------------------- 3. No. of Islands Count no. of islands (land surrounded by water in 4 directions) ---------------------------------------------------- time: O(n^2)  space: O(n^2) No. of islands = no. of graph components ----------------------------------------------------------------------------------------------------------------------------- 4. ...
Read more

35. Graphs-1 (basics)

Image
# Note -  1. it has nodes/vertices (N) connected by edges (E) 2. d egree(N)  = n(edges) connected to a node 3. in-degree(N) = no. of in-going edges  4. out-degree(N) = no. of out-going edges  5.  Total degree of undirected graph = (2*E) 6.  DAG - directed acyclic graph 7.  Path -  a sequence of nodes where all  adj nodes have a direct edge b/w them -------------------------------------------------------------------------------------------------------------------------- 1. Representation- 1. Adjacency Matrix:  space: O(n^2) store info about presence of edges between 2 nodes -------------------------------------------------------- 2. Adjacency list:   space: O(n) - store info about adjacent neighbours of a node - for unweighted graph instead of a pair we will store them as integer array ----------------------------------------------------------------------------------------------------------------------------- 2. BFS- time: O(N+...
Read more