I need to make a stack trace like the one shown below to determine if the braces
ID: 3889228 • Letter: I
Question
I need to make a stack trace like the one shown below to determine if the braces are balanced. I am unsure about how it works exactly. The pseudocode is below the picture.
1. Please explain why and how the braces are changing in each step? -- Why did the brace between b and c disappear in the second step and shift to a backwards brace in the third step (why is a and b together in the third step?)
2. why do the boxes start out as four and decrese by one each time?
3. Why is the last example not balanced?
Input Sming Stock as Algorithm executes stack empty-) 6 alan ced rentheseS 3 po? stack not empty-7 not balances push Stack emply when last "cncouhtered hot balanced 2) Why d, the boxes stort out ot en decrease one at a ime 3 why is the ast exangle not bolonced i 9Explanation / Answer
1.
We traverse through the string.
When we encounter '{', we push '{' into the stack. Hence, each time we encounter '{' , the size of stack increases.
When we encounter '}', we check if the top element of the stack is '{'. If the top element of the stack is '{' then we pop the top element from the stack as we found one pair of ' {} '. If we don't get '{' at the top of te stack, then the string is unbalanced.
The '}' between b and c was cancelled with the '{' on the top of the stack in step 2 and thus we reached to step 3.
And, when we got '}' at the last of the string, cancelled with the '{' on the top of the stack in step 3. Hence, we reached to step 4.
2.
There are 4 braces in { a { b } c }. Hence, two boxes are needed in each step when '{' was pushed into stack. The third box is created when one '{' is popped after matching with '}' between b and c. The fourth box is created when one '{' is popped after matching with '}' after c.
Similarly , three boxes are created in { a { b c } as only three braces and only two boxes in { a b } c }.
3.
The last example is not balanced as the first '{' and '}' cancel each other and the last brace '}' is left. But the stack didn't have '{' to balance the left '}' braces. Hence, the string is unbalanced.