1. Declare a stack st and a vector a;
2. Set count1; //for the first opening bracket
3. FOR i=0: length of string s
IF s[i]=='(' //opening bracket
Append count to a;
Push count to stack st
Increment count;
ELSE IF s[i]==')' //closing bracket
Pop from stack and append to a
ELSE //for other characters
Do nothing
4. Print vector a;
Example with explanation:
Input example 1:
(a+b)/(c+d)
Iteration 0:
i=0
s[i]='('
count=1
append 1 to a
vector status:
1
push 1 to stack st
stack status :
1
increment count
count=2
-----------------------------------------
Iteration 1:
i=1
s[i]='a'
do nothing
vector status:
1
stack status :
1
-----------------------------------------
Iteration 2:
i=2
s[i]='+'
do nothing
vector status:
1
stack status :
1
-----------------------------------------
Iteration 3:
i=3
s[i]='b'
do nothing
vector status:
1
stack status :
1
-----------------------------------------
Iteration 4:
i=4
s[i]=')'
pop from stack and push to a
vector status:
1 , 1
stack status :
empty
-----------------------------------------
Iteration 5:
i=5
s[i]='/'
do nothing
vector status:
1, 1
stack status :
empty
-----------------------------------------
Iteration 6:
i=6
s[i]='('
count=2
append 2 to a
vector status:
1, 1, 2
push 2 to stack st
stack status :
2
increment count
count=3
-----------------------------------------
Iteration 7:
i=7
s[i]='c'
do nothing
vector status:
1, 1, 2
stack status :
2
-----------------------------------------
Iteration 8:
i=8
s[i]='+'
do nothing
vector status:
1, 1, 2
stack status :
2
-----------------------------------------
Iteration 9:
i=9
s[i]='d'
do nothing
vector status:
1, 1, 2
stack status :
2
-----------------------------------------
Iteration 10:
i=10
s[i]=')'
pop from stack and push to a
vector status:
1 , 1, 2, 2
stack status :
empty
Iteration ends as end of string is reached
Algorithm:
Example with explanation:
C++ implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer