Problems

Infix to Postfix

Problem Statement: Covert the given infix expression to postfix expression using stack.

Approach:
Loop the infix expression.

• If the character is an operand, add it to the output.
• If the character is an operator, pop from the stack to the output until the top of the stack has an operator of lower precedence or the stack is empty.
• If the character is a left parenthesis, push it onto the stack.
• If the character is a right parenthesis, pop from the stack to the output until a left parenthesis is at the top of the stack, then pop the left parenthesis from the stack.

fun infixToPostfix(infix: String): String {
    val stack = ArrayDeque<Char>()
    val output = StringBuilder()
    val precedence = mapOf('+' to 1, '-' to 1, '*' to 2, '/' to 2, '^' to 3)

    infix.forEach {
        when {
            it.isLetterorDigit() -> ouput.add(it)
            it == "(" -> stack.addLast(it)
            it == ")" -> {
                while(stack.isNotEmpt() && stack.last() != "(")
                    output.add(stack.removeLast())
                stack.removeLast()
            }
            else -> {
                while(stack.isNotEmpty() && precedence[it] > precedence[stack.last()])
                    output.add(stack.removeLast())
            }
        }
    }
    return output.toString()
}

---

Get Min in O(1)

Problem Statement: Design a stack such that getMinimum() should be O(1)

Approach:
We can use an auxiliary stack that holds the minimum of previous elements, and if an element is removed from the actual stack, we will also do the pop operation on auxiliary stack. To get the minimum, we get the top element in the auxiliary stack. We will create the auxiliary stack along with original stack.

Space can be optimized by only using if the new value is less than or equal to the top of min stack. We pop from min stack only if it equals the removed value from the original stack.

---

Queue using Stacks

Problem Statement: How to implement one queue using two stacks.

Approach:
Maintain 2 stacks S1 & S2.
For enQueue push the element to S1.
For DeQue if S2 is not empty pop from it. Else push all elements from S1 to S2 and then pop from S2. If S1 is also empty throw error.

---

Finding spans

Problem Statement: Given an array A, the span of S[i] of A[i] is the maximum number of consecutive elements A[j] immediately preceding A[i] and such that A[j] \(\le\) A[i]

Approach:
The idea is once we see an element greater than itself, we don't need to look at elements before it. So we only need to keep elements larger the current one in the stack.

fun findingSpans(arr: List<Int>) {
    val stack = ArrayDeque<Int>()
    val spans = IntArray(arr.size)

    arr.forEachIndexed { i, it ->
        while(stack.isNotEmpty() && it > arr[stack.last()]) {
            stack.removeLast()
        }
        val p = if(stack.isEmpty()) - 1 else stack.removeLast()

        spans[i] = i - p
        stack.addLast(i)
    }

    return spans
}

---

Largest Rectangle in Histogram

Problem Statement: Given an array of height of rectangles, find the largest possible rectangle.

Approach:

---

Nearest Greater Element

Problem Statement: Given an array, replace every element with nearset greater element on the right of that element

Approach:
The approach is similar to the finding span problem

fun nextGreaterElement(arr: List<Int>): List<Int> {

}