import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * 사칙 연산 수식 해석 (parse four arithmetic expression) * * @author sunnyk * */ public class FourArithExprParser { // 사칙연산자 목록 private static char[] OPERATORS = { '+', '-', '*', '/' }; // 좌/우 괄호 private static char[] PARENTHESISES = { '(', ')' }; private String numberBuffer; private String inputExpr; private List symbols = new ArrayList(); private Stack aStack = new Stack(); /** * 생성자에 중위식 사칙연산 수식을 입력. */ public FourArithExprParser(String expression) { this.inputExpr = expression; } /** * 중위식 사칙연산 수식에서 항목(symbol)들을 추출한다. */ public void parseSymbols() { // 문자(character) 단위로 분석.. for (int idx = 0; idx < inputExpr.length(); idx++) { char charInExpr = inputExpr.charAt(idx); // 공백(whitespace) 문자 - linefeed, space, tab 등-이면, 이전 버퍼의 내용을 비움. if (Character.isWhitespace(charInExpr)) { handleTempBuff(); } // 사칙연산 연산자 혹은 괄호인 경우, 항목 추가. else if (isMathOperatorOrParenthesis(charInExpr)) { handleTempBuff(); symbols.add(String.valueOf(charInExpr)); } // 숫자 문자인 경우, 숫자 버퍼에 추가.. else if (Character.isDigit(charInExpr)) { if (numberBuffer == null) { numberBuffer = String.valueOf(charInExpr); } else { numberBuffer += charInExpr; } } } handleTempBuff(); } /** * 중위식을 후위식으로 변환. */ public void toPostfix() { List postfixExpr = new ArrayList(); // 중위식 표현식의 각 항목에 대해서... for(String symbol : symbols) { char firstCharOfColumn = symbol.charAt(0); // 피연산자이면, 피연산자를 후위식에 추가 if(!isMathOperatorOrParenthesis(firstCharOfColumn)) { postfixExpr.add(symbol); } // 좌괄호이면 스택에 추가 else if('(' == firstCharOfColumn) { aStack.push(symbol); } // 우괄호이면, 좌괄호 '('가 나올 때까지 스택에서 꺼냄. else if(')' == firstCharOfColumn) { // 스택의 최상위 값이 좌괄호 '('가 아니면.. while (!"(".equals(aStack.peek())) { postfixExpr.add(aStack.pop()); } // while의 끝 // 좌괄호'(' 제거 aStack.pop(); } // 연산자이면, 스택에 있는 더 높은 우선순위 연산자 처리 else { // 만약, 스택이 비어 있거나, 스택의 최상위에 좌괄호가 들어 있으면, 연산자를 스택에 추가 if(aStack.isEmpty() || "(".equals(aStack.peek())) { aStack.push(symbol); } // 연산자의 우선순위가 스택의 최상위에 있는 연산자보다 높으면 스택에 추가 else if(priority(symbol) > priority(aStack.peek())) { aStack.push(symbol); } // 연산자의 우선순위가 스택의 최상위에 있는 연산자와 같으면, 연관에 따라 처리.. // (좌측에서 우측으로 연산하는 경우, 스택의 최상위 연산자를 꺼내고, 연산자를 스택에 추가) else if(priority(symbol) == priority(aStack.peek())) { postfixExpr.add(aStack.pop()); aStack.push(symbol); } // 새로운 연산자의 우선순위가 스택의 최상위에 있는 연산자보다 낮으면, // 스택의 최상위 연산자를 꺼내고, 새로운 연산자를 스택에 추가 else { while(!aStack.isEmpty() && priority(symbol) <= priority(aStack.peek())) { postfixExpr.add(aStack.pop()); } aStack.push(symbol); } } } // 후위식에 스택에 남은 연산자들을 추가 while(!aStack.isEmpty()) { postfixExpr.add(aStack.pop()); } // while의 끝 // 중위식을 후위식으로 덮어쓰기... symbols = postfixExpr; } /** * 후위식 계산을 수행하고 결과 값을 반환한다. */ public int calcalate() { // 후위식 기호(symbol)들을 순차적으로 처리한다. for(String symbol : symbols) { char firstChOfSymbol = symbol.charAt(0); // 사칙연산 연산자인 경우... if(isOperator(firstChOfSymbol)) { // 피연산자(operand)를 스택에서 꺼낸다. // (순서가 반대로 저장되어 있음을 주의할 것) int secondOperand = Integer.valueOf(aStack.pop()); int firstOperand = Integer.valueOf(aStack.pop()); // 연산자의 유형에 따라 계산을 수행한다. int result = 0; switch(firstChOfSymbol) { case '+': result = firstOperand + secondOperand; break; case '-': result = firstOperand - secondOperand; break; case '*': result = firstOperand * secondOperand; break; case '/': result = firstOperand / secondOperand; break; } // 연산 결과를 다시 스택에 담는다. aStack.push(String.valueOf(result)); } // 피연산자인 경우에는 스택에 무조건 담는다. else { aStack.push(symbol); } } // 모든 처리가 끝나면, 결과 값이 스택에 남아 있다. return Integer.valueOf(aStack.pop()); } /** * 수식 분석 결과를 화면에 출력. */ public void print() { for (String symbol : symbols) { System.out.print(symbol + " "); } System.out.println(); } /* * 새로운 항목(symbol)을 찾은 경우, 임시 버퍼의 내용을 항목 목록에 추가 */ private void handleTempBuff() { if (numberBuffer != null) { symbols.add(numberBuffer); numberBuffer = null; } } /* * 연산자 혹은 괄호인지 검사. */ private boolean isMathOperatorOrParenthesis(char inputChar) { for (char op : OPERATORS) { if (inputChar == op) { return true; } } for(char brace : PARENTHESISES) { if (inputChar == brace) { return true; } } return false; } /* * 연산자 인지 검사. */ private boolean isOperator(char inputChar) { for (char op : OPERATORS) { if (inputChar == op) { return true; } } return false; } /* * 연산자의 우선순위(priority)를 반환한다. */ private int priority(String symbol) { int priority = 0; switch(symbol){ case "*": case "/": priority = 2; break; case "+": case "-": priority = 1; } return priority; } }