Question

For the following arithmetic expression:

((2+3)*(4/2))+2

Show step-by-step process for matching parentheses using stack data structure.

Answer 1

Rules for matching parentheses.

1. PUSH in the stack, if encounter opening parenthesis ‘(‘.
2. POP from the stack, if encounter closing parenthesis ‘)’
3. At the end; if stack is empty – Then Parentheses are balanced, otherwise Parentheses are unbalanced.

Given Expression : ( ( 2 + 3 ) * ( 4 / 2 ) ) + 2

Scanning from left to right –

Symbol	Stack, Initially Stack is Empty [ ]	Action
	[ ]
(	(	PUSH ‘(‘
(	( (	PUSH ‘(‘
2	( (	Ignore
+	( (	Ignore
3	( (	Ignore
)	(	POP
*	(	Ignore
(	( (	PUSH
4	( (	Ignore
/	( (	Ignore
2	( (	Ignore
)	(	POP
)	[ ]	POP
+	[ ]	Ignore
2	[ ]	Ignore
End of Symbol