Interview Question
Country: United States
Hey anon, let's consider the following:
A2((AB3)2(C2D)4)5
First, we know that this is equivalent to:
A2((A1B3)2(C2D1)4)5, so let's work from this one for ease of the algorithm.
Stack: 1
We start out with this.
Now, we begin from the right. We will push a (1 * 5) onto the stack. We do this because we know that whatever is to the left of the 5, there will be 5 of it. We encounter a ")" which means that this multiple will affect everything within some parenthesis, so we won't pop it just yet.
Stack : 1/5
Next, we encounter a 4. We know that whatever is left of the 4 will be multiplied by 4, but also , since we have a 5 on top of the stack, multiplied by 5 because of the outside multiple.
Stack: 1/5/20
We encounter a ")" which means to continue since this multiple will apply to whatever is in the parenthesis.
Encounter a 1, so push (20 * 1) on the stack.
Stack: 1/5/20/20
Now, we encounter our first Element (D), and we know that there will be 20 Ds so far. So in our list of Elements, add 20 to D. Since we encountered an element, we can pop off the stack
Stack : 1/5/20
Encounter a 2, so push (2*20) on the stack.
Stack: 1/5/20/40
Now, we see we have Element C, so add 40 to C in the list and pop off the stack:
Stack : 1/5/20
Since we encounter an open parenthesis "(", we pop off the stack signaling that we are done with an encounter of some in parenthesis expression:
Stack : 1/5
Now, we begin on a new parenthesis set, which is succeeded by a "2":
Stack : 1/5/10
Push (3*10),
Stack : 1/5/10/30
Add 30 to B
Pop 30
Stack : 1/5/10
Push(1 * 10)
Stack : 1/5/10/10
Add 10 to A
Pop 10
Stack : 1/5/10
Encounter a "(", pop 10
Stack : 1/5
Encounter another "(", pop 5
Stack : 1
We see a 2, so push (2*1)
Stack : 1/2
Add 2 to A, pop off 2
Stack : 1
We are done.
Final List should look like:
A: 12
B: 30
C: 40
D: 20
Then you can organize however it needs to be empirically
#include <cstdio>
#include <iostream>
#include <stack>
#include <cctype>
#include <cstdlib>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <cassert>
#define INF INT_MAX
#define NIL -1
#define PR(A) cout<<endl<<#A<<" = "<<A<<endl;
#define INF INT_MAX
using namespace std;
typedef vector<vector<int>> matrix;
typedef vector<int> arr;
typedef unsigned int ui;
vector<vector<int>> & make_matrix(int m,int n,int r=0){
vector<vector<int>>&q=*(new vector<vector<int>>);
q.resize(m);
for(auto &i:q){
i.resize(n);
fill(i.begin(),i.end(),r);
}//edn fr
return q;
}//end vector
void printarr(arr &a,int low=0,int high=INT_MAX){
if(high==INT_MAX){
high=a.size()-1;
}//END IF
cout<<endl;
for(int i=low;i<=high;i++){
cout<<a[i]<<' ';
}//end for
}//end [rint
void printmatrix(matrix &a){
for(auto i:a){
cout<<endl;
for(auto j:i){
cout<<j<<" ";
}//end for
}//end for
}//end [rint
void func(string &s){
stack<int>q;
q.push(1);
int i=s.length()-1;
vector<int>count(256,0);
while(i>=0){
if(s[i]=='('){
q.pop();
i--;
}//end if
else if(s[i]==' ')
i--;
else if(isdigit(s[i])){
int k=1;
int num=0;
while(i>=0 && isdigit(s[i])){
num=num+(k*(s[i]-'0'));
i--;
}//end while
while(i>=0 && s[i]==' ')
i--;
if(isalpha(s[i])){
count[s[i]]+=num*q.top();
i--;
}//end if
else{
q.push(num*q.top());
i--;
}//end else
}//end else if
else if(isalpha(s[i])){
count[s[i]]+=q.top();
i--;
}//end else if
}//end while
for(int i=0;i<count.size();i++){
if(count[i]){
cout<<char(i)<<count[i];
}//end for
}//end for
}//end func
int main(){
string s="A2((AB3)2(C2D)4)5";
func(s);
return 0;
}
I've considered this problem more today and I think it's even more simple than what I had originally explained.
- Skor March 18, 2015We will keep one stack, call it s. We first begin by pushing a "1" onto s.
Now, we will start reading the string from the end to the beginning. If we encounter a number, we will multiply this number with the number currently on top of the stack and then push this product onto the stack. When we encounter a close parenthesis ")", we will copy whats on the stack and push on top of the stack. When we encounter an open parenthesis "(", we will pop whatever is on the stack. Finally, when we encounter an element, the number that is currently on top of the stack will be the number of atoms of that element is described by that specific portion of the string.