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:
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 reachedC++ implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer