[백준]1918번 후위표기식

1918번: 후위 표기식
(2시간..)

• 후위 표기법의 장점?

  • 중위 표기법(일상적으로 쓰는 연산식은 중위 표기법으로 표기된 것) → "덧셈"과 "곱셈"의 우선순위 차이가 있음. → 왼쪽부터 차례로 계산하면 잘못된 결과가 나온다.
  • 후위 표기법
    • →순서를 적절히 조절하여 순서를 정해 줄 수 있다.
    • →괄호도 필요 없게 된다
    • a+bc —> abc+ 가 된다.
    • 후위표기법대로라면, "모든 연산자"는 "항상 앞의 두 개 값을 이용" 해 계산하면 된다.

• 중위 표기식 —> 후위 표기식으로 변환하기

  1. 연산자 우선순위 따라 "괄호"로 묶기
  2. 괄호 안의 연산자를 "괄호 오른쪽으로" 옮기기
  3. a+bc → a+(bc) →a+(bc) → a+bc → abc*+
  4. a+bc-D/e → a+ bc -de/ → abc+ - de/ → (abc+de/)- =⇒ abc*+de/-

• 중위표기식 → 후위 표기식으로 고치는 프로그램??

• 문제의 표기식은 "괄호" 가 들어간다.

  A*(B+C) 의 경우
  A*BC+ 
  ABC+* 

풀이생각

A+B*C-D/E 
A+(BC)*-(DE)/
A+BC*-DE/
(ABC*)+-DE/
ABC*+-DE/
(ABC*+DE/)-
1. 우선순위
	A. 최우선 순위 : 괄호 
	B. 두번 째 우선순위 : "*"나 "/"
2. 하나씩 피연산자를 산출한다. 

• 괄호를 마주한다면
  • 괄호다음부터의 것들을 계산하여 피연산자를 리턴
• • 나 / 를 마주한다면
    • 이전 character를 갖고, 피연산자를 리턴한다.

50분이 걸려 "중위 표기식 → 후위표기식"으로 변환하는 IMAGE를 찾아보았다.

수식의 후위 표기법 : 글을 찾아보았다

• 전위 표기법 문제는 풀어 본 적이 있는데 후위 표기법은 어떻게 풀지 생각이 나지 않았다.
• 절차
  1. 피연산자가 들어오면 바로 출력한다.
  2. 연산자가 들어오면, 해당 연산자보다 우선순위가 높거나 같은 "모든 연산자"들을 stack에서 빼내고, 자신을 stack에 담는다.
  3. "("를 만나면, 무조건 스택에 담는다.
  4. ")"를 만나면 "("를 만날 때 까지 stack에서 출력한다.

(((A/(B*C))+(D*E))-(A*C))
-----------
ABC
(((/(*
")"를 마주침
----
ABC*
(((/
")"를 마주침
----
ABC*/
((
----
ABC*/DE
((+(*
")"를 마주침 
-----
ABC*/DE*
((+
")"를 마주침
----
ABC*/DE*+
(
----
ABC*/DE*+AC
(-(*
")"를 마주침 
-----
ABC*/DE*+AC*
(-
")"를 마주침
ABC*/DE*+AC*-

예시2)
A*B*C*D 는 결과 AB*C*D*

package coding;

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

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static String input;
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
    }

    public static void solve(){
    	// *,/는 1 , -,+는 0을 주어 , 이 정수값을 우선순위로 한다. 클 수록 우선순위가 높은 것. 
        Map<String,Integer> map = new HashMap<>();
        map.put("*",1);
        map.put("/",1);
        map.put("+",0);
        map.put("-",0);
        Deque<String> stack = new LinkedList<>();
        String pop ="";
        String cur="";
        int pr =0,curpr=0;
        for(int i=0;i<input.length();i++){
            cur = Character.toString(input.charAt(i));
            // '(' 이면 무조건 stack에 넣는다.
            if(cur.equals("("))stack.add(cur);
            // ')' 이면 stack에 있는 모든 것을 꺼내 append한다. until '('이 나올 때 까지.
            else if(cur.equals(")")){
                while(stack.isEmpty()==false){
                    pop = stack.removeLast();
                    if(pop.equals("("))break;
                    sb.append(pop);
                }
            }
            // 연산자이면 stack 에서 이 연산자보다 우선순위가 높은 애들을 모두 pop && append
            else if(map.containsKey(cur)) {
                curpr = map.get(cur);
                while (stack.isEmpty()==false) {
                    pop = stack.peekLast();
                    if(pop.equals("(")) break;
                    pr = map.get(pop);
                    if(pr<curpr) break;
                    // 이 연산자보다 우선순위가 높은 연산자였다면
                    stack.removeLast();
                    sb.append(pop);
                }
                stack.add(cur);
            }
            // 알파벳은 무조건 append
            else sb.append(cur);

        }
        // Stack에 남은 것을 append
        while(stack.isEmpty()==false){
            String rest = stack.removeLast();
            if(rest.equals("(")) continue;
            sb.append(rest);
        }

    }
    public static void main(String[] args) throws IOException {
        Setting();
        solve();
        System.out.println(sb.toString());

    }

}