백준 1662번: 압축

[문제 링크]

1662번: 압축

---

스택과 재귀를 이용하는 구현 문제였다.

문자열을 탐색하면서 숫자를 만날 경우 스택에 쌓아두고 '(' 를 만날 경우 그 다음 인덱스부터 재귀호출 하여 반환된 값에 스택의 가장 위에 있는 숫자를 곱해주는 방식으로 구현하였다.

---

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int decompress(string& str, int& here) {
	stack<char> stk;

	int ret = 0;

	while (str.size() > here) {
		if (str[here] == '(') {
			ret += (stk.top() - '0') * decompress(str, ++here);
			stk.pop();
		}
		else if (str[here] == ')') {
			here++;
			break;
		}
		else 
			stk.push(str[here++]);
	}
	ret += stk.size();

	return ret;
}

int main(void) {

	string str;
	cin >> str;

	int start = 0;
	cout << decompress(str, start) << endl;

	return 0;
}