import java.util.*;

public class Main {

    public static void main(String[] args) {

        String exp = "1 + 2 * (9 - 5)";

        SuffixExpression se = compile(exp);

        Double result = se.execute();

        System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));

    }

    static SuffixExpression compile(String exp) {

        // TODO:

        Set<String> num_list = Set.of("1", "2", "3", "4", "5", "6", "7", "8", "9", "0");

        Set<String> low_list = Set.of("+", "-");

        Set<String> high_list = Set.of("*", "/");

        Set<String> parentheses_list = Set.of("(", ")");

        Deque<String> stack1 = new LinkedList<>();

        Deque<String> stack2 = new LinkedList<>();

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

            String str = String.valueOf(exp.charAt(i));

            if (num_list.contains(str)) {

                stack2.addFirst(str);

            }

            else if (low_list.contains(str) || high_list.contains(str) || parentheses_list.contains(str)) {

                if (stack1.size() == 0 || Objects.equals(str, "(") || Objects.equals(stack1.getFirst(), "(")) {

                    stack1.addFirst(str);

                    System.out.println(str);

                } else if (Objects.equals(str, ")")) {

                    while (!Objects.equals(stack1.getFirst(), "(")) {

                        stack2.addFirst(stack1.pollFirst());

                    }

                    stack1.pollFirst();

                } else {

                    while (stack1.size() > 0) {

                        if (low_list.contains(stack1.getFirst()) && high_list.contains(str)) {

                            stack1.addFirst(str);

                            break;

                        } else {

                            stack2.addFirst(stack1.pollFirst());

                        }

                    }

                    if (stack1.size() == 0) {

                        stack1.addFirst(str);

                    }

                }

            }

        }

        while (stack1.size() > 0) {

            stack2.addFirst(stack1.pollFirst());

        }

        StringBuffer sb = new StringBuffer();

        while (stack2.size() > 0) {

            sb = sb.append(stack2.pollFirst());

        }

        sb = sb.reverse();

        System.out.println(sb);

        return new SuffixExpression(sb);

    }

}

class SuffixExpression {

    SuffixExpression(StringBuffer sb) {

        this.sb = sb;

    }

    private StringBuffer sb;

    Double execute() {

        // TODO:

        Set<String> num_list = Set.of("1", "2", "3", "4", "5", "6", "7", "8", "9", "0");

        String new_str = String.valueOf(this.sb);

        Deque<Double> stack1 = new LinkedList<>();

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

            String str = String.valueOf(new_str.charAt(i));

            if (num_list.contains(str)) {

                stack1.addFirst(Double.valueOf(str));

            } else {

                var num1 = stack1.pollFirst();

                var num2 = stack1.pollFirst();

                if (Objects.equals("+", str)) {

                    stack1.addFirst(num1 + num2);

                } else if (Objects.equals("-", str)) {

                    stack1.addFirst(num2 - num1);

                } else if (Objects.equals("*", str)) {

                    stack1.addFirst(num1 * num2);

                } else if (Objects.equals("/", str)) {

                    stack1.addFirst(num2 / num1);

                }

            }

        }

        return stack1.pollFirst();

    }

}