[백준 1918] 후위 표기식 (C++/Java)

알고리즘은 다음과 같다.

1) 피연산자 (이 문제에서는 대문자) → 출력

2) 사칙연산 → 스택이 안 비어있고 지금 연산자가 스택 top에 있는 연산자의 우선순위가 더 크거나 같으면 출력. 그리고 지금의 사칙연산 push 

  - 스택이 안 비어있다 : 안에 연산자가 들어있다 → 스택에 들어있는 연산자와 현재 연산자 우선순위를 비교해야한다.

  - 현재 연산자 우선순위 < 스택 top 연산자 우선순위 : 출력 

      ex) 현재 연산자 : + / 스택 연산자 : * => 당연히 우선순위가 높은 연산자부터 계산해야하므로 top에 있는 연산자를 꺼내야함

  - 현재 연산자 우선순위 == 스택 top 연산자 우선순위 : 출력 

      ex) 현재 연산자 : + / 스택 연산자 : - => 우선순위가 동등하다면 먼저 스택에 들어간 연산자부터 계산해야하므로 top에 있는 연산자를 꺼냄

(!st.empty() && (우선순위(현재 연산자) <= 우선순위(st.top()))

3) '(' → push

4) ')' → '('가 나올 때까지 스택을 계속 pop

- C++

#include<iostream>
#include<stack>
using namespace std;
stack<int> st;
int prec(char op){
    switch(op){
            case'(': case')': return 0;
            case'+': case'-': return 1;
            case'*': case'/': return 2;
        }
        return -1;
}
int main(void){
    cin.tie(0); cout.tie(0);
    ios_base :: sync_with_stdio(false);
 
    int n, cur=0; string str, ans="";
    
    cin >> str;
 
    int size = str.length();
        char top_op;
 
        for(int i=0; i<size; i++){
            if('A'<= str[i] && str[i]<='Z'){
                ans += str[i];
            } else if(str[i]=='+' || str[i]=='-' || str[i]=='*' || str[i]=='/'){
                while(!st.empty() && (prec(str[i]) <= prec(st.top()) ) ){
                    ans += st.top();
                    st.pop();
                }
                st.push(str[i]);
            } else if(str[i]=='('){
               st.push('(');
            } 
            else if(str[i]==')'){
                top_op = st.top();
                st.pop();
 
                while(top_op != '('){
                    ans += top_op;
                    top_op = st.top();
                    st.pop();
                }
            }
        }
        
        while(!st.empty()){
            ans += st.top();
            st.pop();
        }
    
    cout << ans;
    
    return 0;
}

-JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
 
public class Main{
    public static int prec(Character op){
        switch(op){
            case'(': case')': return 0;
            case'+': case'-': return 1;
            case'*': case'/': return 2;
        }
        return -1;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Character> st = new Stack<Character>();
 
        String str = br.readLine();
        boolean isOp=false; 
        int size = str.length();
        Character top_op;
 
        for(int i=0; i<size; i++){
            if('A'<= str.charAt(i) && str.charAt(i)<='Z'){
                sb.append(str.charAt(i));
               
            } else if(str.charAt(i)=='+' || str.charAt(i)=='-' || str.charAt(i)=='*' || str.charAt(i)=='/'){
                while(!st.empty() && (prec(str.charAt(i)) <= prec(st.peek()) ) ){
                    sb.append(st.peek());
                    st.pop();
                }
                st.push(str.charAt(i));
            } else if(str.charAt(i)=='('){
               st.push('(');
            } 
            else if(str.charAt(i)==')'){
                top_op = st.pop();
                while(top_op != '('){
                    sb.append(top_op);
                    top_op = st.pop();
                }
            }
        }
       
        while(!st.empty()){
            sb.append(st.peek());
            st.pop();
        }
 
        System.out.print(sb);
    }
}