<Algorithm> 10. 1918번 후위표기식

1. 1918번 후위표기식

• 숫자(문자)는 모두 출력, 연산자들은 스택에 저장

• 스택에 들어있는 연산자들 보다 낮은 우선순위를 가진 연산자가 들어올 경우 스택안에 모든 연산자와 비교하여 우선순위가 높은 연산자들 모두 출력 ex) +(우선순위  2)   [ *(3), /(3),-(2) ] -> * / 출력 -> [ +, - ]

•  '(' 들어올경우 스택에 저장, 그 후에는 위와 똑같은 과정 -->  ')'가 들어오면 스택에 있는 모든 연산자 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        
        Stack stack=new Stack();//중위표현식 입력
        ArrayList arrayList=new ArrayList();
    
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String sig=br.readLine();
        
        for(int i=0;i<sig.length();i++){
        
            switch (sig.charAt(i)){
            
            case '(': //'(' 가 들어올경우 바로 스택에 push
                stack.push(sig.charAt(i));
                break;
                
            case ')': // )가 들어올경우
                while(true){// 스택에 있는 모든 연산자 출력
                 if((char)stack.peek()=='('){stack.pop();break;}//'('경우 반복종료
                 System.out.print(stack.pop());
                }
                break;
                
            case '*':    
            case '/':
            case '+':    
            case '-':    
                while(!stack.isEmpty()&&priority((char)stack.peek())>=priority(sig.charAt(i))){
                    System.out.print(stack.pop());
                }//스택안에 모든 연산자와 우선순위를 비교하여 들어오는 연산자보다 
                    스택안에 있는 연산자의 우선순위가 높을 경우 모두 pop
 
                stack.push(sig.charAt(i));// 우선순위 높은게 위에 있어야함
                break;
            default:
                System.out.print(sig.charAt(i));//숫자(문자)는 출력
                break;
            }            
        }
      
        while(!stack.isEmpty()){ // 반복문 끝나고 스택안에 모두 출력
            System.out.print(stack.pop());
        }
    }
    public static int priority(char ch){ //우선순위
        int pri=0; 
        
        switch (ch) {// 가장낮은 우선순위 '('은 ')'만날때까지 출력하면 안됨 
        case '(':
        case ')':
            pri=1;
            break;
        case '+':
        case '-':
             pri=2;
             break;
        case '*':
        case '/':
            pri=3;
            break;
        default:
            pri=0;
            break;
        }
        
        return pri;
    }
    
}
 

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