[백준] 1918번 후위표기식

1918번 후위표기식

1. 이해하기

• 중위 표기식을 후위 표기식으로 바꾸는 문제.
• 스택을 어떻게 사용하는지 알아야 하는 문제이다.

---

2. 구현하기

• 현재 값이 알파벳이라면 출력하는 배열에 넣어준다.
• 현재 값이 +,- 라면 ( 이외의 연산자는 모두 빼고 출력하는 배열에 넣어준다. 그 이후 스택의 가장 윗부분에 현재 값을 넣어준다.
• 현재 값이 *,/ 라면 +,-,( 이외의 연산자는 모두 빼어 출력하는 배열에 넣어준다. 이후, 스택의 가장 윗부분에 현재 값을 넣어준다.
• 현재 값이 ( 라면 스택의 가장 윗부분에 넣는다.
• 현재 값이 ) 라면 ( 이 나올 때까지 빼어 출력하는 배열에 넣어준 후, (를 빼버린다.

package algo;

import java.util.Scanner;

public class Acm1918_후위표기식 {
    static char[] stk1;
    static char[] stk2;
    static int stk1Idx = -1;
    static int stk2Idx = -1;
    static String str;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        str = sc.next();
        stk1 = new char[110];
        stk2 = new char[110];

        for(int i = 0; i < str.length(); i++) {
            char here = str.charAt(i);
            if('A' <= here && here <= 'Z') {
                stk1[++stk1Idx] = here;
            } else {
                if(here == '+' || here == '-') {
                    while(stk2Idx >= 0 && stk2[stk2Idx] != '(') {
                        stk1[++stk1Idx] = stk2[stk2Idx];
                        --stk2Idx;
                    }
                    stk2[++stk2Idx] = here;
                } else if(here == '*' || here == '/') {
                    while(stk2Idx >= 0 && stk2[stk2Idx] != '(' && stk2[stk2Idx] != '+' && stk2[stk2Idx] != '-') {
                        stk1[++stk1Idx] = stk2[stk2Idx];
                        --stk2Idx;
                    }
                    stk2[++stk2Idx] = here;
                } else if(here == '(') {
                    stk2[++stk2Idx] = here;
                } else if(here == ')') {
                    while(stk2Idx >= 0 && stk2[stk2Idx] != '(') {
                        stk1[++stk1Idx] = stk2[stk2Idx--];
                    }
                    stk2Idx--;
                }
            }
        }
        while(stk2Idx >= 0) {
            stk1[++stk1Idx] = stk2[stk2Idx--];
        }
        for(int i = 0; i <= stk1Idx; i++) {
            System.out.print(stk1[i]);
        }
    }
}

---