먼저 풀어보면 피연산자 A와 B는 스택에 넣은 후 , 연산자 +를 만나면 스택에서 pop을 수행해 피연산자 2개, A와 B를 꺼내어 각각 변수에 담은 뒤 + 연산을 계산하고 계산된 결과 값을 다시 스택에 넣는다.
수식이 끝났다면 스택에는 하나의 값이 저장되어있을 텐데(올바른 수식이였다면) 그것이 수식의 최종 결과가 된다.
여기서 주의해야할 점은 스택은 후입선출, Last-in First-out이므로 위와같이 A 와 B를 차례대로 스택에 넣었다면, B와 A 순서대로 pop이 될 것이다. 여기서 첫번째로 나왔다고 B + A 이렇게 그냥 나온 순서대로 수식을 계산하게 되면 덧셈이나 곱셈은 상관 없지만 뺄셈과 나눗셈에는 틀린 결과 값이 나오게 된다. 때문에 계산할 때 피연산자들의 위치를 잘 맞춰줘야한다.
후위 표기식의 계산 알고리즘을 설계하면 다음과 같다.
1. 피연산자면 스택에 push한다.
2. 연산자를 만나면 pop을 두번하고 각각 값을 저장한 후, 연산자에 맞는 계산을 한다.
3. 계산을 한 뒤, 결과 값은 다시 스택에 넣는다. 이 과정을 수식이 끝날 때 까지 반복한다.
4. 수식이 끝났다면 스택에 마지막 남은 값이 결과 값이 된다.
실제 식을 사용해 후위 표기식을 계산해보자.
중위 표기식 2 * ( 4 + 5 ) -> 후위 표기식 2 4 5 + *
1. 2는 피연산자이므로 스택에 push한다.
2. 4는 피연산자이므로 스택에 push한다.
3. 5는 피연산자이므로 스택에 push한다.
4. +는 연산자. 스택에서 pop()을 2번 수행해 각각 값을 변수에 담고 더한다. 이후 스택에 결과 값을 push한다. (위 계산식에서 5+4라고 했는데 실제론 4+5로 수행해야함)
5. *는 연산자. 스택에서 pop()을 2번 수행해 각각 값을 변수에 담고 곱한다. 이후 스택에 결과값을 push한다.(4번과 마찬가지로 2*9로 수행해야함)
6. 수식이 끝났으므로 스택에 마지막 남은 값을 pop한다. 그 값이 최종 결과 값이다.
후위 표기식 계산 원리가 이해가 갔다면 이제 실제 코드도 구현할 수 있을 것이다!
package basic;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;
import javax.naming.event.ObjectChangeListener;
public class Calc {
private Object c;
/**
* 문자열로 들어온 수식을 ArrayList로 분할합니다.
* @param expr
* @return 수식을 피연산자,연산자로 분할한 ArrayList
*/
private ArrayList splitTokens (String expr) {
String[] exp = expr.split(""); // String -> String[]
ArrayList tokens = new ArrayList();
int value = 0;
String op = "";
boolean flag = false;
for(String c:exp) { // foreach문 (배열,ArrayList)
if(c.equals(" ")) {
continue;
}
if("0123456789".contains(c)) {
value = value * 10 + Integer.parseInt(c);
flag = true;
}else {
if(flag) {
tokens.add(value);
value = 0;
}
flag = false;
tokens.add(c);
}
}
if(flag) {
tokens.add(value);
}
return tokens;
}
/**
* 중위 표기식을 후위 표기식으로 변경합니다
* @param tokens 중위 표기식 ArrayList
* @return 후위 표기식 ArrayList
*/
private ArrayList infixToPostfix(ArrayList tokens) {
ArrayList result = new ArrayList();
HashMap prec = new HashMap();
Stack opStack = new Stack();
prec.put("*", 3);
prec.put("/", 3);
prec.put("+", 2);
prec.put("-", 2);
prec.put("(", 1);
for(Object c:tokens) {
if(c.equals("(")) {
opStack.push(c);
}else if(c.equals(")")) {
while(!opStack.peek().equals("(")) {
Object val = opStack.pop();
if(!val.equals("(")) {
result.add(val);
}
}
opStack.pop();
}else if(prec.containsKey(c)) {
if(opStack.isEmpty()) {
opStack.push(c);
}else {
if(prec.get(opStack.peek()) >= prec.get(c)) {
result.add(opStack.pop());
opStack.push(c);
}else {
opStack.push(c);
}
}
}else {
result.add(c);
}
}
while(!opStack.isEmpty()) {
result.add(opStack.pop());
}
return result;
}
/**
* 후위 표기식을 계산합니다.
* @param expr 후위 표기식 ArrayList
* @return 최종 계산 결과
*/
private int postFixEval(ArrayList expr) {
Stack valueStack = new Stack();
for(Object c:expr) {
if(c instanceof Integer) {
valueStack.push((Integer) c);
}else if(c.equals("+")){
int num1 = valueStack.pop();
int num2 = valueStack.pop();
valueStack.push(num2+num1);
}else if(c.equals("-")){
int num1 = valueStack.pop();
int num2 = valueStack.pop();
valueStack.push(num2-num1);
}else if(c.equals("*")){
int num1 = valueStack.pop();
int num2 = valueStack.pop();
valueStack.push(num2*num1);
}else if(c.equals("/")){
int num1 = valueStack.pop();
int num2 = valueStack.pop();
valueStack.push(num2/num1);
}
}
int result = valueStack.pop();
return result;
}
public int process(String expr) {
ArrayList postfix = infixToPostfix(splitTokens(expr)); // 중위 표기식을 후위 표기식으로 변경
int result = postFixEval(postfix); // 후위 표기 수식 계산
return result;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
String expr = sc.nextLine();
Calc calc = new Calc();
int result = calc.process(expr);
System.out.println(result);
}
}
