문제
수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.
이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.
중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.
예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.
다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.▼
이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오.
입력
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.
출력
첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오.
문제 링크
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
풀이
후위 표기법의 계산 방식을 이용해서 구현해주면 된다.
후위 표기법
후위 표기법이란?
후위 표기법은 수식의 표현법 중 하나로, 연산자가 피연산자들 뒤에 위치하는 표기법을 말한다.
우리가 일상에서 사용하는 수식은 중위 표기법으로, 연산자가 피연산자들 중간에 위치하는 표기법이다.▼
후위 표기법의 작동
후위 표기법은 스택을 통해 계산을 수행한다.
수가 들어오면 push(x), 연산자가 들어오면 스택에서 수 두개를 pop()하는 식으로 계산이 수행된다.▼
프로그램 동작
그래서 후위 표기법이 수행되는 것 처럼, 우리도 중위 표기식을 스택을 이용해 후위 표기식으로 바꿀 것이다.
아래의 예제를 후위 표기식으로 바꿔보겠다.
- A*(B+C)
1. 문자열을 순서대로 탐색한다.
이 때 탐색한 문자가 수(여기에선 알파벳이다.)라면 정답에 바로 넣어준다. ▼
2. 다음 문자로 넘어가본다.
이번 문자는 '*' 연산자이다.
'*'나 '/'의 경우 '+'와 '-'보다 우선순위가 높다.
만약 스택이 비어있지 않고 현재 문자가 '*'나 '/'라면, 자신과 우선순위가 같은 연산자가 스택의 가장 뒤에 있는지 확인해본다.
만약 있다면 먼저 pop해버린다.
그리고 현재 문자인 '*' 또는 '/'를 넣는 과정을 해준다.
하지만 스택이 비어있으므로, 현재 문자를 스택에 넣어주기만 한다. ▼
3. 그 다음에는 열린 괄호가 있다.
중위 연산자의 경우 괄호에 있는 값부터 연산해야하기 때문에, 체크를 해야한다.
일단 스택에 괄호를 넣어줌으로 현재 괄호가 시작했다는 것을 알려준다.▼
4. 이번에는 수에 해당하는 문자가 왔으므로 정답에 바로 넣어준다.▼
5. 다음에는 '+' 연산자를 확인해본다.
'+'나 '-'의 경우 '*'와 '/'보다 우선순위가 낮다.
괄호 내부에서 연산자들이 존재하고 현재 만난 '+'나 '-' 연산자보다 먼저 나온 연산자가 있다면, 먼저 나온 연산자들은 현재 연산자보다 먼저 수행이 되어야한다.
따라서, '+'나 '-' 연산자가 등장하게 되면 스택에 있는 연산자들을 열린 괄호 전까지 전부 pop해서 정답에 넣어준다.
만약 스택에 아무것도 없거나 괄호 다음에 들어온 연산자가 없다면, 그냥 +를 넣어준다.▼
6. 다음에는 수에 해당하는 문자가 왔으므로 정답에 바로 넣어준다.▼
7. 마지막으로는 닫힌 괄호가 왔다.
닫힌 괄호가 오면, 열린 괄호 전까지의 모든 연산자를 pop해서 정답에 붙여준다.
그리고 열린 괄호는 스택에서 제거해준다.▼
8. 이렇게 문자열의 끝에 도달했다고 끝을 내버리면 앞에 나왔던 연산자가 적용이 안된채로 답을 도출해버리게 된다.
따라서 스택이 빌 때 까지 정답에 스택에 있는 연산자를 pop해서 정답에 붙여준다.▼
9. 마지막에 전부 pop해주는 과정까지 했다면, 정답에 들어있는 문자열이 답이 된다.
Swift 코드
let str = readLine()!.map{ String($0) }
var answer = ""
var stack = [String]()
for i in str {
if i >= "A", i <= "Z" {
answer += i
} else {
switch i {
case "(":
stack.append(i)
case "*", "/":
while !stack.isEmpty {
if stack.last! == "*" || stack.last! == "/" {
answer += stack.popLast()!
} else {
break
}
}
stack.append(i)
case "+", "-":
while !stack.isEmpty {
if stack.last! != "(" {
answer += stack.popLast()!
} else {
break
}
}
stack.append(i)
case ")":
while !stack.isEmpty {
if stack.last! != "(" {
answer += stack.popLast()!
} else {
break
}
}
stack.popLast()!
default:
stack.append(i)
}
}
}
while !stack.isEmpty {
answer += stack.popLast()!
}
print(answer)