Algorithm_Practice/16228.java at master · ktyu/Algorithm_Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine().trim();

        // 후위 표기식으로 바꿔서 큐에 넣기
        Queue<String> converted = new LinkedList<>();

        String s;
        Stack<String> temp = new Stack<>();
        for(int i=0; i<str.length(); i++) {
            if(Character.isDigit(str.charAt(i))) { // number
                StringBuffer num = new StringBuffer();
                num.append(str.charAt(i));
                while(++i < str.length() && Character.isDigit(str.charAt(i)))
                    num.append(str.charAt(i));
                i--;
                converted.offer(num.toString());
            }

            else if(str.charAt(i) == '(') {
                temp.push("(");
            }

            else if(str.charAt(i) == ')') {
                s = temp.pop();
                while(!(s.equals("("))) {
                    converted.offer(s);
                    s = temp.pop();
                }
            }

            else if(str.charAt(i) =='<' || str.charAt(i) =='>'){
                if(temp.isEmpty())
                    temp.push(String.valueOf(str.charAt(i++))); // skip '?'
                else {
                    while(!(temp.isEmpty()) && (temp.peek().equals("<") || (temp.peek().equals(">"))))
                        converted.offer(temp.pop());
                    temp.push(String.valueOf(str.charAt(i++))); // skip '?'
                }
            }

            else { // '+' or '-'
                if(temp.isEmpty())
                    temp.push(String.valueOf(str.charAt(i)));
                else {
                    while(!(temp.isEmpty()) && !(temp.peek().equals("(")))
                        converted.offer(temp.pop());
                    temp.push(String.valueOf(str.charAt(i)));
                }
            }
        }
        // 스택에 남아있는 것들 처리
        while(!temp.isEmpty())
            converted.offer(temp.pop());


        // 큐에 후위표기식으로 들어가 있는 식을 하나씩 꺼내면서 계산, temp 스택은 비어있는게 보장되므로 재사용함
        while(!converted.isEmpty()) {
            // 연산자인 경우
            if(converted.peek().equals("<") || converted.peek().equals(">") || converted.peek().equals("+") || converted.peek().equals("-")) {

                char op = converted.poll().charAt(0);
                int a = Integer.valueOf(temp.pop());
                int b = Integer.valueOf(temp.pop());

                if(op == '<') {
                    if(a<b) temp.push(String.valueOf(a));
                    else temp.push(String.valueOf(b));
                }

                else if(op == '>') {
                    if(a>b) temp.push(String.valueOf(a));
                    else temp.push(String.valueOf(b));
                }

                else if(op == '+')
                    temp.push(String.valueOf(a+b));

                else if(op == '-')
                    temp.push(String.valueOf(b-a));
            }

            // 숫자일 경우 스택에 저장
            else {
                temp.push(converted.poll());
            }
        }
        // 최종 결과 출력
        System.out.println(temp.pop());
    }
}