문제 정의
수학 표현식이 담긴 문자열 str을 첫 번째이자 유일한 인수로 받는 자바스크립트 함수를 작성해야 합니다.
함수의 목표는 연산자와 피연산자의 순서와 의미를 그대로 유지하면서 표현식에서 모든 괄호를 제거하는 것입니다.
예를 들어, 함수의 입력이 다음과 같다면 −
입력
const str = 'u-(v-w-(x+y))-z';
출력
const output = 'u-v+w+x+y-z';
접근 방법: 스택(Stack) 활용
괄호를 제거할 때 가장 중요한 점은 괄호가 사라지면서 내부 항들의 부호가 바뀔 수 있다는 것입니다. 특히 마이너스(-) 기호 뒤에 오는 괄호를 제거하면 내부의 모든 부호가 반전되어야 합니다.
이 문제는 스택 자료구조를 사용하면 깔끔하게 해결할 수 있습니다. 스택에는 결과 문자열의 요소들이 쌓이며, 괄호 안으로 들어갈 때마다 이전 부호를 추적하여 중첩된 괄호에 따른 부호 변화를 처리합니다.
알고리즘 동작 원리
- 여는 괄호 '(' 또는 닫는 괄호 ')': 스택의 마지막 부호를 기준으로 현재 유효 부호(
lastSign)를 갱신합니다. - '+' 기호: 스택의 마지막 요소가 부호가 아니라면 현재 유효 부호를 추가합니다.
- '-' 기호: 이전 부호와 결합하여 부호를 계산합니다. 마이너스 × 마이너스 = 플러스 규칙이 적용됩니다.
- 피연산자(변수): 별도의 처리 없이 그대로 스택에 추가합니다.
구현 예제
다음은 전체 코드입니다 −
const str = 'u-(v-w-(x+y))-z';
const removeParentheses = (str = '') => {
let stack = []
let lastSign = '+'
for (let char of str) {
if (char === '(' || char === ')') {
lastSign = stack[stack.length - 1] || '+'
} else if (char === '+') {
if (stack[stack.length - 1] !== '-' && stack[stack.length - 1] !== '+') {
stack.push(lastSign)
}
} else if (char === '-') {
if (lastSign === '-') {
if (stack[stack.length - 1] === '-') stack.pop()
stack.push('+')
} else {
if (stack[stack.length - 1] === '+') stack.pop()
stack.push('-')
}
} else {
stack.push(char)
}
}
return stack.join('').replace(/^\+/, '')
};
console.log(removeParentheses(str));코드 단계별 설명
- 결과를 저장할 빈 배열
stack과 초기 부호lastSign = '+'를 선언합니다. - 문자열을 한 글자씩 순회하면서 괄호, 연산자, 피연산자를 구분하여 처리합니다.
- 괄호를 만나면 스택의 마지막 부호를 참조해 유효 부호를 갱신함으로써 중첩 괄호의 부호 변화를 자연스럽게 반영합니다.
- 모든 순회가 끝나면 스택의 요소들을 하나의 문자열로 합치고, 맨 앞에 불필요한 '+'가 있다면 제거한 후 반환합니다.
실행 결과
u-v+w+x+y-z
입력 표현식 u-(v-w-(x+y))-z에서 괄호가 모두 제거되고, 부호가 올바르게 정리된 결과를 확인할 수 있습니다. 이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 효율적입니다.