Stack Practice Questions

Given the precedence $\wedge > \times > + > -$ and associativity rules, evaluate $a + b \times c - d \wedge e \wedge f$ as follows:

1. Evaluate right-associative $\wedge$: $d \wedge e \wedge f \rightarrow d \wedge (e \wedge f) \rightarrow def \wedge \wedge$.
2. Evaluate $\times$ (left associative): $b \times c \rightarrow bc \times$.
3. Evaluate $+$ (precedence higher than $-$): $a + (bc \times ) \rightarrow abc \times +$.
4. Evaluate $-$ (left associative): $(abc \times +) - (def \wedge \wedge) \rightarrow abc \times + def \wedge \wedge -$.

The final postfix expression is $abc \times + def \wedge \wedge -$.

To generate permutations from the input sequence $a, b, c, d$ using a stack, we must follow the Last-In-First-Out (LIFO) property. For the string "cabd", we must first push $a, b, c$ and pop $c$. The stack now contains $[a, b]$, with $b$ at the top. To access $a$, we are forced to pop $b$ first, meaning the sequence must contain $b$ before $a$ whenever $a$ and $b$ are both in the stack. Consequently, after $c$ is popped, the next character must be $b$ or $d$, making it impossible to output $a$ before $b$. Thus, the string "cabd" cannot be generated.

In an array $A[1 \dots \text{MAXSIZE}]$, $Stack_1$ grows forward from index $1$, while $Stack_2$ grows backward from index $\text{MAXSIZE}$.
The variable $top1$ points to the topmost element of $Stack_1$, and $top2$ points to the topmost element of $Stack_2$.
The remaining empty space between the stacks is represented by the indices between $top1$ and $top2$.
The array is "stack full" when no additional elements can be pushed, which occurs when the two pointers are adjacent.
This adjacency condition is mathematically expressed as $top1 = top2 - 1$.

To derive the average stack-life, we first determine the stack-life $L_m$ for each element $m \in \{1, \dots, n\}$.
The end time of Push(m) is $E_m = (m-1)(X+Y) + X$.
The operations sequence is $n$ pushes followed by $n$ pops, with a delay $Y$ after every operation. The end of the last Push(n) occurs at $T = nX + (n-1)Y$. The Pop operations follow, where Pop(m) is the $(n-m+1)$-th pop.
The start time of the $k$-th pop is $S_k = T + Y + (k-1)(X+Y)$. Substituting $k = n-m+1$:
$S_m = [nX + (n-1)Y] + Y + (n-m)(X+Y) = (n-1)(X+Y) + X + Y + (n-m)(X+Y)$
The stack-life $L_m = S_m - E_m$:
$L_m = [(n-1)(X+Y) + X + Y + (n-m)(X+Y)] - [(m-1)(X+Y) + X] = (2n - 2m)(X+Y) + Y$
The average stack-life is the sum over $m=1$ to $n$ divided by $n$:
$\text{Avg} = \frac{1}{n} \sum_{m=1}^{n} [(2n-2m)(X+Y) + Y] = \frac{X+Y}{n} \sum_{m=1}^{n} (2n-2m) + Y$
Using the sum of the first $n-1$ integers $\sum_{j=0}^{n-1} 2j = 2\frac{(n-1)n}{2} = n(n-1)$:
$\text{Avg} = \frac{X+Y}{n} [n(n-1)] + Y = (n-1)(X+Y) + Y = nX - X + nY = n(X+Y) - X$

Evaluating expressions without embedded function calls can be efficiently performed by converting the expression into postfix notation (Reverse Polish Notation). In this approach, we process each token sequentially from left to right. When an operand is encountered, it is pushed onto a stack. When an operator is encountered, the necessary number of operands are popped, the operation is computed, and the resulting value is pushed back onto the stack. Since this method relies solely on a single stack to store intermediate values $v_i$, one stack is sufficient for evaluation.

The conversion of an infix expression to postfix, commonly implemented via the Shunting-yard algorithm, processes tokens sequentially. Operands (like $A$ or $B$) are immediately appended to the output string as they appear. Operators are pushed onto a single stack, which serves to hold them until their precedence and associativity rules are satisfied relative to subsequent operators. This stack efficiently manages operator ordering to ensure the correct postfix sequence is generated, eliminating the need to stack operands. Thus, only an operator stack is essential.

To convert the infix expression $A+B*(C+D)/F+D*E$ to postfix, we follow the operator precedence (BODMAS):

1. Parentheses: $(C+D)$ becomes $CD+$.
2. Multiplication/Division (left-to-right): $B*(CD+)/F$ becomes $BCD+*F/$.
3. First Addition: $A + (BCD+*F/)$ becomes $ABCD+*F/+$.
4. Remaining Multiplication: $D*E$ becomes $DE*$.
5. Second Addition: Adding $(DE*)$ to $(ABCD+*F/+)$ results in $ABCD+*F/DE*++$.

To obtain the permutation $3, 4, 5, 2, 1$ from the input sequence $1, 2, 3, 4, 5$ using a stack, we perform these operations based on the Last-In-First-Out (LIFO) principle:

1. Push $1, 2, 3$ into the stack, then Pop $3$.
2. Push $4$ into the stack, then Pop $4$.
3. Push $5$ into the stack, then Pop $5$.
4. Pop the remaining elements from the stack: $2$ then $1$.
   This sequence of operations results in the exact output order $3, 4, 5, 2, 1$, confirming the permutation is achievable.

To determine the sequence of values popped, we trace the stack operations step-by-step:

1. PUSH(10), PUSH(20): Stack is $[10, 20]$. POP results in $20$, stack becomes $[10]$.
2. PUSH(10), PUSH(20): Stack becomes $[10, 10, 20]$. POP results in $20$, stack becomes $[10, 10]$.
3. POP, POP: Removes $10$ then $10$, leaving an empty stack.
4. PUSH(20), POP: Stack becomes $[20]$, then $20$ is popped.
   The combined sequence of popped values is $20, 20, 10, 10, 20$.