49. Stack-2: pre,in,post-fix

Priority order of operators:       (^)    >    ( *, / )    >    (+, -)
----------------------------------------------------------------------------------------------------------------------------

NOTE-
1. learn: infix to postfix

2. infix to prefix is modified infix to postfix, since u just reverse string & replace brackets & do postfix conversion with some conditions & reverse the postfix answer

3. for other conversions:⭐⭐
we try to traverse from that side where we find 2 operands before an operator
-----------------------------------------------------------------------------------------------------------------------------

Infix to Postfix-⭐

time: O(2n),  space: O(2n)

we need- 1. (variable i)
                2. (stack st)
                3. (variable ans)

1. iterate through infix expression
2. if u see an operand, insert it into ans
3. if u see an operator & stack == empty, then push it into a stack
4. if u see an operator & stack != empty,  then :
         if curr priority > st.top()   => push curr into stack
         if curr priority <= st.top() => pop out from stack and add to ans, repeat till u hit above cond
5.  if u encounter ( push it
6. if u encounter ) remove everything from stack & add to ans till u get ( and also remove ( then again pop & add to ans


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

Infix to Prefix-

1. reverse given string & make     ( to )     &     ) to (
2. do infix to postfix conversion
3. reverse the answer

change: if, curr priority < st.top() => only then do pop out of stack & add to ans till curr >= st.top
here, curr can be any operator except ^

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

Postfix to Infix-

time: O(n),      space: O(n)

1. iterate from left to right
2. store operands into a stack
3. if u encounter an operator- pick last 2 elements from stack--> put operator in b/w them--> wrap in brackets-->push back this shit into stack

(2nd top # 1st top),   where # is operator

when iteration is over, stack only contains 1 element which is my answer


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

Prefix to Infix-

time: O(n),   space:O(n)

iterate from right to left
this time store as, ( 1st top # 2nd top )


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

Postfix to Prefix-

1. push operands into stack
2. if u see operator, do ( # top2 top1 ) into stack after popping out top2 and top1


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

Prefix to Postfix-

1. start from back
2. if operand, push into stack
3. if operator, pop out last 2 top elements, do ( top1 top2 # )
 

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

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more