Cal 3 - NDDCoder

[Problem]

Create a program which converts a character string of calculation formula to a postfix expression and calculates it.

For example, a character string “3+(4+5)*6+7” can be converted to a postfix expression "345+6*+7+".

The calculation should yield 64.

The operators used in the formula are ‘+’ and ‘*’. Parentheses can be used in the formula. The operands are the integers between 0 ~ 9. The parentheses are always paired properly.

[Input]

The first line of the input file provides the length of the test case. The test cases are given in the next lines. Total of 10 test cases are given.

[Output]

The output file outputs the test case number following the ‘#’ symbol. It is followed by a space, and then the answer.

[Input Example]

113
(9+(5*2+1)+(3*3*7*6*9*1*7+1+8*6+6*1*1*5*2)*4*7+4*3*8*2*6+(7*8*4*5)+3+7+(2+6+5+1+7+6+7*3*(6+2)+6+6)*2+4+2*2+4*9*3)

85
(4+8+4*(8*5*(7*(6*8)+3+(6+(3+7+1*7*5*4)*3)*2*3+5)+6+7*7)*4+2+9*4+7+2*3*(7*6*1*8)+9+9)

[Output Example]

#1 672676
#2 1974171

import java.util.Scanner;

public class PostfixCalculator {
    static int precedence(char op) {
        if (op == '*') return 2;
        if (op == '+') return 1;
        return 0;
    }

// Convert infix to postfix
    static String toPostfix(String expr) {
        char[] stack = new char[1000];
        int top = -1;
        StringBuilder postfix = new StringBuilder();

for (int i = 0; i < expr.length(); i++) {
            char ch = expr.charAt(i);
            if (Character.isDigit(ch)) {
                postfix.append(ch);
            } else if (ch == '(') {
                stack[++top] = ch;
            } else if (ch == ')') {
                while (top >= 0 && stack[top] != '(') {
                    postfix.append(stack[top--]);
                }
                top--; // pop '('
            } else if (ch == '+' || ch == '*') {
                while (top >= 0 && precedence(stack[top]) >= precedence(ch)) {
                    postfix.append(stack[top--]);
                }
                stack[++top] = ch;
            }
        }
        while (top >= 0) {
            postfix.append(stack[top--]);
        }

return postfix.toString();
    }

// Evaluate postfix expression
    static int evaluatePostfix(String postfix) {
        int[] stack = new int[1000];
        int top = -1;

for (int i = 0; i < postfix.length(); i++) {
            char ch = postfix.charAt(i);
            if (Character.isDigit(ch)) {
                stack[++top] = ch - '0';
            } else {
                int b = stack[top--];
                int a = stack[top--];
                int result = 0;
                if (ch == '+') result = a + b;
                else if (ch == '*') result = a * b;
                stack[++top] = result;
            }
        }

return stack[top];
    }

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int t = 1; t <= 10; t++) {
            int len = sc.nextInt();
            sc.nextLine(); // consume newline
            String expr = sc.nextLine();

String postfix = toPostfix(expr);
            int result = evaluatePostfix(postfix);

System.out.println("#" + t + " " + result);
        }
    }
}