c++ solution, modified from the solution https://leetcode.com/problems/decode-string/discuss/472087/0ms-C%2B%2B-solution-using-one-stack
string expandedString (string inputStr)
{
stack st;
for (int i = 0; i < inputStr.size(); i++) {
if (inputStr[i] != '}') {
st.push(inputStr[i]);
}
else {
// for calculating num
string number = "";
while (!st.empty() && isdigit(st.top())) {
number = st.top() + number;
st.pop();
}
st.pop(); // pop '{'
st.pop();// pop')'
int num = stoi(number);
// get string to times
string curr_str = "";
while (st.top() != '('){
curr_str = st.top() + curr_str;
st.pop();
}
st.pop(); // pop '('
while (num--) {
for (int p = 0; p < curr_str.size(); p++) {
st.push(curr_str[p]);
}
}
}
}
string s = "";
while (!st.empty()) {
s = st.top() + s;
st.pop();
}
return s;
}