So we actually need to parse the entire expression and whenever we are receiving an opening bracket we need to memorize its occurrence. So, we need a stack actually.
Pre-requisite:
String s – which is to be parsed
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 reached
So we actually need to parse the entire expression and whenever we are receiving an opening bracket we need to memorize its occurrence. So, we need a stack actually.
Pre-requisite:
String s – which is to be parsed
Algorithm:
Example with explanation:
C++ implementation:
Output