๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ’ปTech/โ˜•Java

[Java] ๊ณ„์‚ฐ๊ธฐ ์†Œ์Šค (๊ด„ํ˜ธ, ์‚ฌ์น™์—ฐ์‚ฐ ์šฐ์„ ์ˆœ์œ„)

by _viper_ 2015. 9. 16.
๋ฐ˜์‘ํ˜•

๊ด„ํ˜ธ, ์‚ฌ์น™์—ฐ์‚ฐ ์šฐ์„ ์ˆœ์œ„ ์ฒ˜๋ฆฌํ•˜๋Š” ๊ณ„์‚ฐ๊ธฐ ์†Œ์Šค ๊ณต์œ ํ•ฉ๋‹ˆ๋‹ค.

ํ›„์œ„ํ‘œ๊ธฐ๋ฒ•๊ณผ Stack ๊ธฐ๋ฐ˜์œผ๋กœ ๊ตฌํ˜„ํ–ˆ์Šต๋‹ˆ๋‹ค.

 

์™„๋ฒฝํ•˜๊ฒŒ ์˜ˆ์™ธ์ฒ˜๋ฆฌ ๋œ ๋ถ€๋ถ„์ด ์•„๋‹ˆ๋ผ ์ฐธ๊ณ ํ•˜์‹œ๋ฉด ์ข‹๊ฒ ์Šต๋‹ˆ๋‹ค.

package test;

import java.util.ArrayList;
import java.util.Stack;

/**
 * ๊ณ„์‚ฐ ์„œ๋น„์Šค
 * 
 * @author
 * @version
 * @since
 * @created 2015. 1. 12.
 */
public class CalculatorService {

    public static void main(String[] args) {

        String result = getCalculate("(10 + 20) * 10");
        System.out.println(result);
    }

    /**
     * ๊ณ„์‚ฐ์ฒ˜๋ฆฌ
     */
    private static String getCalculate(String content) {

        char[] operationCode = {'+', '-', '*', '/', '(', ')'}; //์—ฐ์‚ฐ ๋ถ€ํ˜ธ

        ArrayList<String> postfixList = new ArrayList<String>(); //ํ›„์œ„ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ๋ณ€ํ™˜ ํ›„ ์ €์žฅ ํ•  ArrayList
        Stack<Character> opStack = new Stack<Character>(); // ์—ฐ์‚ฐ ๋ถ€ํ˜ธ ์šฐ์„ ์ˆœ์œ„์ฒ˜๋ฆฌ ํ•˜๋ฉฐ ํ›„์œ„ ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ๋ณ€๊ฒฝํ•˜๋Š” Stack
        Stack<String> calculatorStack = new Stack<String>(); //ํ›„์œ„ ํ‘œ๊ธฐ๋ฒ•์„ ๊ณ„์‚ฐํ•˜๋Š” Stack

        int index = 0;//content.substring() ์ธ์ˆ˜

        for (int i = 0; i < content.length(); i++) {
            for (int j = 0; j < operationCode.length; j++) {
                if (content.charAt(i) == operationCode[j]) { //๋ฌธ์ž์—ด๊ณผ ์—ฐ์‚ฐ ๋ถ€ํ˜ธ ๋น„๊ต

                    //postfixList์— ์—ฐ์‚ฐ ๋ถ€ํ˜ธ๊ฐ€ ๋‚˜์˜ค๊ธฐ ์ „๊นŒ์ง€์˜ ์ˆซ์ž๋ฅผ ๋‹ด๋Š”๋‹ค(๊ณต๋ฐฑ์ œ๊ฑฐ)
                    postfixList.add(content.substring(index, i).trim().replace("(", "").replace(")", ""));
                    if (content.charAt(i) == '(') {
                        if (content.charAt(i) == ')') {//์šฐ ๊ด„ํ˜ธ๊ฐ€ ๋‚˜์˜ค๋ฉด ์ขŒ ๊ด„ํ˜ธ๊ฐ€ ๋‚˜์˜ค๊ฑฐ๋‚˜ ์Šคํƒ์— ๋น„์–ด์žˆ์„๋•Œ ๊นŒ์ง€ popํ•˜์—ฌ list์— ์ €์žฅ
                            while (true) {
                                postfixList.add(opStack.pop().toString());
                                if (opStack.pop() == '(' || opStack.isEmpty()) {
                                    break;
                                }
                            }
                        }
                    }

                    if (opStack.isEmpty()) { //opStack์ด ๋น„์–ด ์žˆ์„ ๊ฒฝ์šฐ
                        opStack.push(operationCode[j]); //์—ฐ์‚ฐ ๋ถ€ํ˜ธ ์ €์žฅ
                    } else { //opStack์ด ๋น„์–ด ์žˆ์ง€ ์•Š์„ ๊ฒฝ์šฐ
                        if (opOrder(operationCode[j]) > opOrder(opStack.peek())) { //์šฐ์„  ์ˆœ์œ„ ๋น„๊ต
                            opStack.push(operationCode[j]); //์Šคํƒ์— top ๊ฐ’ ๋ณด๋‹ค ๋†’์€ ์šฐ์„ ์ˆœ์œ„์ด๋ฉด ๊ทธ๋Œ€๋กœ ์ €์žฅ
                        } else if (opOrder(operationCode[j]) <= opOrder(opStack.peek())) {//์šฐ์„  ์ˆœ์œ„ ๋น„๊ต
                            postfixList.add(opStack.peek().toString());//์Šคํƒ์— ์žˆ๋Š” ๊ฐ’์ด ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ™๊ฑฐ๋‚˜ ์ž‘์„ ๊ฒฝ์šฐ list์— ์ €์žฅ
                            opStack.pop();//์Šคํƒ ์ œ๊ฑฐ
                            opStack.push(operationCode[j]);//๋†’์€ ์šฐ์„ ์ˆœ์œ„ ์—ฐ์‚ฐ ๋ถ€ํ˜ธ ์Šคํƒ์— ์ €์žฅ
                        }
                    }
                    index = i + 1;// ๋‹ค์Œ ์ˆœ์„œ ์ฒ˜๋ฆฌ
                }
            }
        }
        postfixList.add(content.substring(index, content.length()).trim().replace("(", "").replace(")", "")); //๋งˆ์ง€๋ง‰ ์ˆซ์ž ์ฒ˜๋ฆฌ

        if (!opStack.isEmpty()) { //Stack์— ๋‚จ์•„์žˆ๋Š” ์—ฐ์‚ฐ ๋ชจ๋‘ postfixList์— ์ถ”๊ฐ€
            for (int i = 0; i < opStack.size();) {
                postfixList.add(opStack.peek().toString());
                opStack.pop();
            }
        }

        //list์— ๊ณต๋ฐฑ, ๊ด„ํ˜ธ ์ œ๊ฑฐ
        for (int i = 0; i < postfixList.size(); i++) {
            if (postfixList.get(i).equals("")) {
                postfixList.remove(i);
                i = i - 1;
            } else if (postfixList.get(i).equals("(")) {
                postfixList.remove(i);
                i = i - 1;
            } else if (postfixList.get(i).equals(")")) {
                postfixList.remove(i);
                i = i - 1;
            }
        }

        System.out.println(postfixList);

        opStack.clear(); //Stack ๋น„์šฐ๊ธฐ

        //postfixList๋ฅผ calculatorStack์— ์ €์žฅํ•˜๋ฉด์„œ ํ›„์œ„์—ฐ์‚ฐ ์ฒ˜๋ฆฌ
        for (int i = 0; i < postfixList.size(); i++) {
            calculatorStack.push(postfixList.get(i));
            for (int j = 0; j < operationCode.length; j++) {
                if (postfixList.get(i).charAt(0) == operationCode[j]) { //์—ฐ์‚ฐ ๋ถ€ํ˜ธ ๋น„๊ต
                    calculatorStack.pop(); //stack์— ์ €์žฅ๋œ ์—ฐ์‚ฐ ๋ถ€ํ˜ธ ์ œ๊ฑฐ
                    double s2, s1; //stack์—์„œ pop ๋˜๋Š” ๊ฐ’๋“ค์„ ์ €์žฅํ•  ๋ณ€์ˆ˜
                    String rs; // ์—ฐ์‚ฐ ์ฒ˜๋ฆฌ ํ›„ ๋ฌธ์ž์—ด๋กœ ๋ณ€ํ™˜ ํ›„ stack์— ์ €์žฅํ•  ๋ณ€์ˆ˜

                    s2 = Double.parseDouble(calculatorStack.pop()); //์Šคํƒ์—์„œ popํ•˜์—ฌ ๋ฌธ์ž์—ด์„ ์ˆซ์ž๋กœ ํ˜•๋ณ€ํ™˜
                    s1 = Double.parseDouble(calculatorStack.pop());

                    //์—ฐ์‚ฐ ๋ถ€ํ˜ธ์— ํ•ด๋‹นํ•˜๋Š” ์‚ฐ์ˆ  ์ฒ˜๋ฆฌ ํ›„ stack์— ์ €์žฅ
                    switch (operationCode[j]) {
                        case '+':
                            rs = String.valueOf(s1 + s2);
                            calculatorStack.push(rs);
                            break;
                        case '-':
                            rs = String.valueOf(s1 - s2);
                            calculatorStack.push(rs);
                            break;
                        case '*':
                            rs = String.valueOf(s1 * s2);
                            calculatorStack.push(rs);
                            break;
                        case '/':
                            rs = String.valueOf(s1 / s2);
                            calculatorStack.push(rs);
                            break;
                    }
                }
            }
        }

        double re = Double.parseDouble(calculatorStack.peek()); //Stack Top ๋ฐ์ดํ„ฐ 
        String result = String.format("%.10f", re); //์†Œ์ˆ˜์  10์งธ์งœ๋ฆฌ

        //์ •์ˆ˜ ๋ถ€๋ถ„ ์ž๋ฆฌ ๊ตฌํ•˜๊ธฐ
        int num = 0;
        for (int i = 0; i < result.length(); i++) {
            if (result.charAt(i) == '.') {
                num = i;
                break;
            }
        }

        //์ •์ˆ˜๋ถ€๋ถ„
        String mok = result.substring(0, num);

        //๋‚˜๋จธ์ง€ ์—ฐ์‚ฐ
        double divde = Double.parseDouble(result) % Double.parseDouble(mok);

        //๋‚˜๋จธ์ง€๊ฐ€ 0์ด๋ฉด ์†Œ์ˆ˜์  ์ž๋ฆฟ ์ˆ˜ ์•ˆ๋ณด์ด๊ฒŒ
        if (divde == 0) {
            result = String.format("%.0f", re);
        }

        return result;
    }

    /**
     * ์—ฐ์‚ฐ ๋ถ€ํ˜ธ ์šฐ์„ ์ˆœ์œ„ ์ •ํ•˜๋Š” ๋ฉ”์„œ๋“œ
     * 
     * @param op - ์—ฐ์‚ฐ ๋ถ€ํ˜ธ
     */
    public static int opOrder(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return -1;
        }
    }

}

 

 

๊ณ„์‚ฐ ๊ฒฐ๊ณผ

[10, 20, +, 10, *]
300