package myfirstjava;

import java.util.ArrayList; import java.util.Scanner; import java.util.StringTokenizer;

class GStack { static int top; Object[] stck;

public GStack() {
    top = 0;
    stck = new Object[200];
}

public T peek() {
    if (top == 0)
        return null;
    else
        return (T) stck[top];
}

public void push(T item) {
    if (top == 200)
        return;
    stck[top] = item;
    top++;
}

public T pop() {
    if (top == 0)
        return null;
    top--;
    return (T) stck[top];
}

}

public class Postfix { private static int PIS(String temp) {

    if (("^").equals(temp))
        return 4;
    if (("*").equals(temp) || ("/").equals(temp))
        return 3;
    if (("+").equals(temp) || ("-").equals(temp))
        return 2;
    if ((")").equals(temp))
        return 1;
    if (("(").equals(temp))
        return 0;
    return 0;
}

private static int PIE(String temp) {
    if (("(").equals(temp))
        return 5;
    if (("^").equals(temp))
        return 4;
    if (("*").equals(temp) || ("/").equals(temp))
        return 3;
    if (("+").equals(temp) || ("-").equals(temp))
        return 2;
    if ((")").equals(temp))
        return 1;
    if (("=").equals(temp) || ("    ").equals(temp))
        return -1;
    return 0;
}

static String IntoPost(StringTokenizer st) {
    GStack<String> stringStack = new GStack<String>();
    int n = st.countTokens();
    ArrayList<String> a = new ArrayList<String>(n);
    for (int i = 0; i < n; i++) {
        String token = st.nextToken();
        try {
            Double.parseDouble(token);
            a.add(token);
            System.out.print(token + " ");

        } catch (NumberFormatException e) {
        }

        switch (token) {
        case ")":
            while (!("(").equals(stringStack)) {
                a.add(stringStack.peek());

                System.out.print(stringStack.pop() + " ");
            }
            stringStack.pop();
            break;

        case "+":
        case "*":
        case "-":
        case "/":
        case "(":
            if (PIS(stringStack.peek()) >= (PIE(token))) {
                while (stringStack.top != 0) {
                    a.add(stringStack.peek());

                    System.out.print(stringStack.pop() + " ");
                }
            }
            stringStack.push(token);
            break;

        case "=":
            while (stringStack.top != 0) {
                a.add(stringStack.peek());
                System.out.print(stringStack.pop() + " ");
            }
        }
    }

    String Postfix = String.join("    ", a);
    return Postfix;
}

static double Evaluation(String s) {
    GStack<Double> DoubleStack = new GStack<Double>();
    StringTokenizer st = new StringTokenizer(s, " ");
    int n = st.countTokens();
    double temp = 0;
    double op1, op2;
    for (int i = 0; i < n; i++) {
        String token = st.nextToken();
        if ((token.equals("+") == false) && (token.equals("-") == false) && (token.equals("*") == false)
                && (token.equals("/") == false)) {
            try {
                temp = Double.parseDouble(token);
                DoubleStack.push(temp);
            } catch (NumberFormatException e) {

            }
        } else {
            op2 = DoubleStack.pop();
            op1 = DoubleStack.pop();

            switch (token) {
            case "+":
                DoubleStack.push(op1 + op2);
                break;
            case "-":
                DoubleStack.push(op1 - op2);
                break;
            case "*":
                DoubleStack.push(op1 * op2);
                break;
            case "/":
                DoubleStack.push(op1 / op2);
                break;
            }
        }
    }
    return temp;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    System.out.print("수식: ");
    String Postfix = in.nextLine();
    StringTokenizer st = new StringTokenizer(Postfix, "+ *(    /-)^=", true);
    String postFix = IntoPost(st);
    double result = Evaluation(postFix);
    System.out.print("    답 : " + result);
    in.close();
}

}