백준 1918번: 후위 표기식

문제

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

---

풀이

스택을 이용하여 연산자가 피연산자 사이에 있는 중위 표기식을 연산자가 피연산자 앞에 있는 후위 표기식으로 바꾸는 문제입니다. 후위 표기식은 중위 표기식과 다르게 연산자의 우선순위가 없어서 순서대로 계산하면 되기 때문에 주로 프로그램 내부의 표기법으로 사용된다고 합니다.

또한 이 문제에서는 피연산자가 숫자가 아니라 1개의 문자이기 때문에 숫자의 자릿수를 생각하지 않아도 됩니다.

---

코드

C언어

문자열 str을 입력받으면 i를 포함한 for문을 i가 입력받은 문자열의 길이가 될 때까지 실행합니다. 그 전에 각 중위 표기식의 연산자에는 우선순위가 있기 때문에 prec 함수를 통해 이러한 우선순위를 표현합니다. 연산자는 아니지만 괄호로 인하여 연산의 우선순위가 바뀌는 경우도 있기 때문에 열린괄호('(')의 우선순위를 가장 낮게 설정합니다. 따라서 더하기와 빼기('+', '-')의 우선순위는 2번째로 높게, 그리고 나머지('*', '/')의 우선순위를 가장 높게 설정합니다.

for문 안에서 i번째 문자 str[i]가 피연산자('A'~'Z')라면 그대로 출력합니다. 따라서 스택에는 오직 괄호 혹은 연산자만 들어갑니다. 열린 괄호('(')라면 스택에 push하고 닫힌괄호(')')라면 스택의 최상단에 있는 연산자가 열린 괄호가 나올 때까지 출력하고 스택에서 열린괄호를 삭제(pop)합니다. 연산자('+', '-', '*', '/')라면 스택이 비어있지 않고 최상단에 있는 문자의 우선순위가 현재 연산자(str[i])보다 크거나 같을 때까지 출력한 후에 현재 연산자를 스택에 push합니다.

for문이 종료되면 스택에 남은 연산자를 순서대로 모두 pop해가며 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char stack[100];
int idx = -1;
void push(char value) {
	stack[++idx] = value;
}
char pop() {
	if (idx < 0) return -1;
	else return stack[idx--];
}
int is_empty() {
	if (idx == -1) return 1;
	else return 0;
}
char peek() {
	if (is_empty()) return 0;
	else return stack[idx];
}
int prec(char op) {
	if (op == '(') return -1;
	else if (op == '+' || op == '-') return 0;
	else return 1;
}
main() {
	char str[101];
	scanf("%s", str);
	for (int i = 0; i < strlen(str); i++) {
		if (str[i] >= 'A' && str[i] <= 'Z') {
			printf("%c", str[i]);
		}
		else if (str[i] == '(') {
			push(str[i]);
		}
		else if (str[i] == ')') {
			while (peek() != '(') {
				printf("%c", pop());
			}
			pop();
		}
		else {
			while (!is_empty() && prec(peek()) >= prec(str[i])) {
				printf("%c", pop());
			}
			push(str[i]);
		}
	}
	while (!is_empty()) {
		printf("%c", pop());
	}
}

자바

위의 C언어를 이용한 풀이와 동일하지만 스택을 따로 구현하지는 않고 자바 util 패키지의 Stack 클래스를 이용하였습니다. 또한 Stringbuilder를 이용하여 한꺼번에 출력하였습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static int prec(char op) {
        if (op == '(') return -1;
        else if (op == '+' || op == '-') return 0;
        else return 1;
    }

    public static void main(String[] args) throws IOException {
        Stack<Character> stack = new Stack<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') {
                sb.append(str.charAt(i));
            } else if (str.charAt(i) == '(') {
                stack.push(str.charAt(i));
            } else if (str.charAt(i) == ')') {
                while (stack.peek() != '(') {
                    sb.append(stack.pop());
                }
                stack.pop();
            } else {
                while (!stack.empty() && prec(stack.peek()) >= prec(str.charAt(i))) {
                    sb.append(stack.pop());
                }
                stack.push(str.charAt(i));
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        System.out.println(sb);
    }
}

 

---

결론

후위 표기식이란 개념이 처음에는 생소했지만 직접 구현해보는 과정을 통해서 우선순위 없이 순서대로 계산한다는 큰 장점이 있다는 것을 알게 되었고 스택과 같은 자료구조를 잘 활용하면 이보다 어려운 응용문제도 쉽게 풀 수 있을 것 같다는 생각을 하게 되었습니다.