후위 표현식 만들기 (stack) - java

후위 표현식

후위 표현식을 만들기 위해서는 연산자의 순서 우선순위를 알아두면 좋다

3가지로 구분해서 외우면 편할거 같은데

icp 연산에서 ( 는 우선순위가 3이라 가장 높다 따라서 ( 들어갈때는 무조건 스택에 쌓으면 된다

다음 *, / 연산은 *,/ 만났을때만 꺼내고 나머지는 쌓는다

+,- 연산은 *,/,+,- 만났을때 꺼내고 나머지는 쌓는다

) 는 ( 만날때 까지 꺼내고 만약  stack[top]==( 면 ( 삭제하기 위해서  top을 한번더 빼준다.

마지막으로는 스택에 남은 모든 값들을 출력해주면 후위표현식이 만들어 진다.

* 진짜 개 꿀팁 -

후위 표현식을 만들고 계산을 해야하는데 나오는 값을 다른 배열에 넣지말고 

String a ="";

이런 문자열 하나 만들어서 그 뒤에 계속 문자열로 붙여주면 진짜 쉽게 만들 수 있다

/**

* 계산기 : 중위표현식 => 후위 표현식으로 변환해서 출력

* icp : in-coming priority

*

* isp : in-stack priority

*

* 숫자가 클수록 우선순위가 높다

*

* 토큰 isp icp 비교 ) ( 나올때 까지 꺼냄 * / 2 2 + - 1 1 ( 0 0 스택에 무조건 넣기

*

* input 피연산자, 연산자 합쳐서 13개 입력 ( 6 + 5 * ( 2 - 8 ) / 2 )

*

* output 6 5 2 8 - * 2 / +

*

*/

public class 후위연산만들기 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        char[] stack = new char[20]; //연산자만 저장

        int top=-1;

        String[] str = sc.nextLine().split(" ");

        

        

        for(int i=0; i<str.length; i++) {

            char c =str[i].charAt(0);

            

            switch(c) {

            

            case '(': //들어가는 ( 괄호는 우선순위가 3이라 잴 높다 그래서 무조건 스택에 쌓는다

                stack[++top]=c;

                break;

            case '*': // *, / 는 우선순위가 2이다 스택에 나보다 우선순위가 작은것이 남아있을때 까지 출력한다

            case '/': // 여기서 *, / 보다 우선순위가 같거나 높은 경우는 *,/ 밖에 없다 그건 꺼내고 나머지는 쌓는다

                while(top>-1 &&(stack[top]== '*' || stack[top]=='/')) {

                    System.out.print(stack[top]+" ");

                    top--; //꺼낸다

                }

                stack[++top]=c;

                break;

                

            case '+': // + - 보다 우선순위가 낮은 경우는 없기 때문에 다 출력한다

            case '-':

                while(top>-1 && (stack[top]=='*' || stack[top]=='/' || stack[top]=='+' || stack[top]=='-')) {

                    System.out.print(stack[top]+" ");

                    top--;

                }

                

                stack[++top]=c;

                break;

            case ')': // ( 만날때 까지 출력한다.

                while(top > -1 && stack[top]!='(') {

                    System.out.print(stack[top]+" ");

                    top--;

                }

                if(stack[top]=='(') {

                    top--;

                }

                break;

            default:

                System.out.print(str[i]+" ");

                break;

            }

        }

        

        while(top > -1) {

            System.out.println(stack[top--]+" ");

        }

        

    }

}