백준 1935번: 후위 표기식2

문제

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

1935번: 후위 표기식2

---

풀이

후위 표기식과 각 피연산자에 대응하는 값들을 입력받고 그 결과를 구하는 문제입니다.

---

코드

C언어

스택에 괄호 혹은 연산자만 들어갈 수 있었던 후위 표기식 문제와 달리 이 문제에서 스택에는 숫자만 들어갈 수 있습니다. 나눗셈을 한 후의 값이 정수가 아닐 수도 있기 때문에 double형 배열로 스택을 표현했습니다.

후위 표기식을 문자열 str에 입력받고 i를 포함한 for문에서 str의 i번 인덱스의 값(str[i])이 알파벳(피연산자)이라면 해당 알파벳에 할당된 값을 스택에 push합니다. str[i]가 연산자라면 연산을 실행할 두 수를 pop하여 받고 해당 연산을 실행한 후의 값을 스택에 push합니다.

모든 연산을 마친 후에 결과값인 스택에 남은 1개의 숫자를 pop하여 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
double stack[100];
int idx = -1;
void push(double value) {
	stack[++idx] = value;
}
double pop() {
	return stack[idx--];
}
main() {
	int n;
	char str[101];
	scanf("%d", &n);
	int* value = (int*)malloc(sizeof(int) * n);
	scanf("%s", str);
	for (int i = 0; i < n; i++) {
		scanf("%d", &value[i]);
	}
	for (int i = 0; i < strlen(str); i++) {
		if ('A' <= str[i] && str[i] <= 'Z') {
			push(value[str[i] - 'A']);
		}
		else if (str[i] == '+') {
			double b = pop();
			double a = pop();
			push(a + b);
		}
		else if (str[i] == '-') {
			double b = pop();
			double a = pop();
			push(a - b);
		}
		else if (str[i] == '*') {
			double b = pop();
			double a = pop();
			push(a * b);
		}
		else if (str[i] == '/') {
			double b = pop();
			double a = pop();
			push(a / b);
		}
	}
	printf("%.2lf", pop());
}

 

자바

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

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

public class Main {
    public static void main(String[] args) throws IOException {
        Stack<Double> stack = new Stack<Double>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        double[] value = new double[n];
        String str = br.readLine();
        for (int i = 0; i < n; i++) {
            value[i] = Double.parseDouble(br.readLine());
        }
        for (int i = 0; i < str.length(); i++) {
            if ('A' <= str.charAt(i) && str.charAt(i) <= 'Z') {
                stack.push(value[str.charAt(i) - 'A']);
            } else if (str.charAt(i) == '+') {
                double b = stack.pop();
                double a = stack.pop();
                stack.push(a + b);
            } else if (str.charAt(i) == '-') {
                double b = stack.pop();
                double a = stack.pop();
                stack.push(a - b);
            } else if (str.charAt(i) == '*') {
                double b = stack.pop();
                double a = stack.pop();
                stack.push(a * b);
            } else if (str.charAt(i) == '/') {
                double b = stack.pop();
                double a = stack.pop();
                stack.push(a / b);
            }
        }
        System.out.print(String.format("%.2f", stack.pop()));
    }
}

 

---

결론

중위 표기식을 후위 표기식으로 변환하는 방법을 알고 후위 표기식을 계산하는 방법을 알고 있으니 중위 표기식을 후위 표기식으로 변환하여 계산할 수 있게 됐습니다. 이 과정을 통하여 프로그램 내부에서의 연산 과정을 조금이나마 이해하게 되었습니다.