(3 * 4.5) - (1 * 5) 또는 3 * 4.5 - 1 * 5
위와 같은 수식은 사람이 보기엔 논리적으로 간단하게 풀 수 있으나 컴퓨터의 경우 어떤 연산자가 더 우선순위가 높은지 판단하기
어렵기 때문에 컴퓨터가 인식할 수 있는 문장으로 바꾸어 줄 필요가 있다. 이때 필요한 방법이 후위 표기법이다.
중위 표기법
- 인간이 일반적으로 사용하는 수식의 표현 방법.
- "피연산자 '연산자' 피연산자" 순으로 표현되어 있는 방식(연산자가 피연산자 가운데 있는 방식)
- 예) (3 * 1) - 2
후위 표기법
- 컴퓨터가 알기 쉽게 표현한 방식
- 연산자의 위치가 수식 뒤쪽에 표현된다. 피연산자1 연산자 피연산자2 => 피연산자1 피연산자2 연산자
- 예) 3 * 1 => 3 1 *
예) 1 - 3 * 2 => 1 - (3 2)* => 1 3 2 * -
중위 표기법에서 후위 표기법으로 변환하는 알고리즘
- 에드거 다익스트라(Edsger Dijkstra)가 고안한 알고리즘. 동작 과정은 다음과 같다.
1) 입력받은 중위 표기식에서 토큰을 읽는다.
2) 토큰이 피연산자이면 토큰을 결과에 출력한다.
3) 토큰이 연산자(괄호 포함)일 때, 이 토큰이 스택의 최상위 노드에 저장되어 있는 연산자보다
우선순위가 높으면(왼쪽 괄호는 우선순위가 가장 낮지만 예외적으로 항상 스택에 삽입)
스택에 삽입하고, 그렇지 않다면 토큰보다 우선순위가 같거나 낮은 연산자를 만날때까지
스택에 제거연산을 수행하여 출력한다.(같은 것도 제거한다.) 그리고 제거연산이 끝나면 토큰을 스택에 삽입한다.
4) 토큰이 오른쪽 괄호 ')' 이면 최상위 노드에 왼쪽 괄호 '('가 올 때까지 스택에 제거 연산을
수행하고 제거한 노드에 담긴 연산자를 출력한다. 왼쪽 괄호를 만나면 제거만 하고 출력하지 않는다.
5) 중위 표기식에서 더 읽을 것이 없다면 빠져나간다음 스택이 빌 때까지 제거연산을 수행하고,
더 읽을 것이 있다면 1부터 다시 반복한다.
* 연산자의 우선순위를 비교하는 이유 : 아래와 같이 괄호가 없는 경우 사람은 우선순위를 판별하여 계산할 수 있으나
컴퓨터는 불가능하기 때문이다.
예) 1 - 3.334 * 5 + 2 / 3
후위 표기식을 계산하는 알고리즘
- 표기식을 왼쪽에서부터 오른쪽으로 하나씩 읽는다.
- 해당 문자가 피연산자(숫자)이면 스택에 집어 넣고 연산자이면 이전에 넣어뒀던 피연산자 2개를 꺼내 순서대로 계산한다.
- 예) 1 3 2 * -
1) '1' 은 피연산자이므로 스택에 집어 넣는다. (스택 : '1')
2) '3' 은 피연산자이므로 스택에 집어 넣는다. (스택 : '1', '3')
3) '2' 는 피연산자이므로 스택에 집어 넣는다. (스택 : '1', '3', '2')
3) '*' 은 연산자이므로 스택에서 두 번의 제거연산을 통해 '2' 과 '3' 을 꺼낸 다음 '2 * 3' 연산을 수행한다.
그리고 수행한 결과를 다시 스택에 집어 넣는다. (스택 : '1', '6')
4) '-' 은 연산자이므로 스택에서 3)과 같이 제거 연산을 통해 '1'과 '6' 을 꺼낸 다음 '1 - 6' 연산을 수행하고
그 결과를 다시 스택에 집어 넣는다. (스택 : '-5')
5) 스택에는 최종 결과만 남아 있으므로 스택에서 꺼내면 계산 결과를 얻게 된다.
public class Node { private String data; private Node nextNode; public Node(String data) { this.data = data; } public String getData() { return data; } public void setNextNode(Node nextNode) { this.nextNode = nextNode; } public Node getNextNode() { return nextNode; }}
public class LinkedListStack {
private Node top; // tail
private Node list; // head
// 노드 추가
public void push(Node newNode) {
// 스택이 비어있을 경우
if (list == null)
list = newNode;
// 스택이 비어있지 않으면
else {
// top(꼬리)을 찾아 연결한다.
Node currentTop = list;
while (currentTop.getNextNode() != null)
currentTop = currentTop.getNextNode();
currentTop.setNextNode(newNode);
}
top = newNode;
}
// 노드 제거
public Node pop() {
Node popped = top;
// 제거할 노드가 head와 같다면 스택을 비운다.
if (list == popped) {
list = null;
top = null;
} else {
// 그렇지 않다면 top을 갱신
Node currentTop = list;
while (currentTop.getNextNode() != popped)
currentTop = currentTop.getNextNode();
top = currentTop;
top.setNextNode(null);
}
return popped;
}
// 최상위 노드 반환
public Node getTop() {
return top;
}
// 스택 사이즈 반환
public int getSize() {
Node currentTop = list;
int count = 0;
while (currentTop != null) {
currentTop = currentTop.getNextNode();
count++;
}
return count;
}
// 노드가 비어있는지 확인
public boolean isEmpty() {
return list == null;
}
}
public class Calculator {
private final char[] NUMBER = { '0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', '.' };
private final char OPERAND = 'O';
private final char LEFT_PARENTHESIS = '(';
private final char RIGHT_PARENTHESIS = ')';
private final char MULTIPLY = '*';
private final char DIVIDE = '/';
private final char PLUS = '+';
private final char MINUS = '-';
private char[] token;
private int tokenType;
private LinkedListStack stack;
public Calculator() {
stack = new LinkedListStack();
}
// 연산자에 대해 우선순위를 매기는 함수
public int getPriority(char operator, boolean inStack) {
int priority = -1;
switch (operator) {
case LEFT_PARENTHESIS:
// 왼쪽 괄호의 경우 항상 예외로 스택에 넣어준다.
// 스택에 들어있는 왼쪽 괄호
if (inStack)
priority = 3;
else
priority = 0;
break;
case MULTIPLY:
case DIVIDE:
priority = 1;
break;
case PLUS:
case MINUS:
priority = 2;
break;
}
return priority;
}
// 토큰과 우선순위 비교하는 함수
public boolean isPrior(char operatorInToken, char operatorInStack) {
return (getPriority(operatorInToken, false) < getPriority(
operatorInStack, true));
}
// 해당 토큰이 숫자인지 판별하는 함수
public boolean isNumber(char token) {
for (int i = 0; i < NUMBER.length; i++)
if (token == NUMBER[i])
return true;
return false;
}
// 중위표기식에서 토큰을 추출하는 함수(토크나이징)
public int getNextToken(String infixExpression, char[] chrArray) {
int i = 0;
infixExpression += ' ';
// null이 나올때까지 반복
for (i = 0; infixExpression.charAt(i) != 0; i++) {
// 문자를 하나씩 추출한다.
chrArray[i] = infixExpression.charAt(i);
// 피연산자이면 타입을 표시
if (isNumber(chrArray[i])) {
tokenType = OPERAND;
// 만약 피연산자 다음의 문자가 피연산자가 아니라면 중지
if (!isNumber(infixExpression.charAt(i + 1)))
break;
} else {
// 연산자이면 대입한다.
tokenType = infixExpression.charAt(i);
break;
}
}
// 추출된 토큰을 복사한다.
token = new char[++i];
for (int j = 0; j < i; j++)
token[j] = chrArray[j];
return i;
}
// 중위 -> 후위표기법 변환 함수
public String getPostfix(String infixExpression) {
StringBuffer postfixExpression = new StringBuffer();
int position = 0;
int length = infixExpression.length();
char[] chArr = new char[length];
Node popped;
// 문자열을 다 읽을때까지 반복
while (position < length) {
// position 위치부터 토큰을 하나씩 가져온다.
position += getNextToken(infixExpression.substring(position), chArr);
// 추출된 토큰의 타입이 피연산자라면 출력
if (tokenType == OPERAND) {
postfixExpression.append(token);
postfixExpression.append(' ');
} else {
// 연산자가 오른쪽 괄호 ')' 라면 스택에서 '('가 나올때까지 제거연산 수행
if (tokenType == RIGHT_PARENTHESIS) {
while (!stack.isEmpty()) {
popped = stack.pop();
// 제거한 노드가 '(' 라면 중지
if (popped.getData().charAt(0) == LEFT_PARENTHESIS)
break;
else
postfixExpression.append(popped.getData());
}
}
// 나머지 연산자의 경우 토큰의 우선순위가 스택의 top보다 낮을 경우 제거연산 수행.
// 제거연산은 토큰의 우선순위보다 낮은 노드가 나올때까지 수행(같은 거라도 수행)
else {
// 스택이 비어있지 않고 토큰의 우선순위가 스택의 top보다 낮다면
while (!stack.isEmpty()
&& !isPrior(token[0], stack.getTop().getData()
.charAt(0))) {
// 제거연산 수행
popped = stack.pop();
// '(' 빼고 모두 출력
if (popped.getData().charAt(0) != LEFT_PARENTHESIS)
postfixExpression.append(popped.getData());
}
// 토큰의 우선순위가 스택의 top보다 높다면 삽입연산 수행
stack.push(new Node(String.valueOf(token)));
}
}
}
// 스택에 남아 있는 노드들을 제거연산한다.
while (!stack.isEmpty()) {
popped = stack.pop();
// '(' 빼고 모두 출력
if (popped.getData().charAt(0) != LEFT_PARENTHESIS)
postfixExpression.append(popped.getData());
}
return postfixExpression.toString();
}
// 계산
double calculate(String postfixExpression) {
int position = 0;
int length = postfixExpression.length();
char[] chrArr = new char[length];
double result = 0.0;
double operand1, operand2;
LinkedListStack stack = new LinkedListStack();
while (position < length) {
position += getNextToken(postfixExpression.substring(position),
chrArr);
// 공백은 패스
if (tokenType == ' ')
continue;
// 피연산자이면 스택에 삽입
if (tokenType == OPERAND) {
stack.push(new Node(String.valueOf(token)));
} else {
// 연산자이면 스택에서 제거연산을 두 번 수행 후
operand2 = Double.parseDouble(stack.pop().getData());
operand1 = Double.parseDouble(stack.pop().getData());
// 연산
switch (tokenType) {
case MULTIPLY:
result = operand1 * operand2;
break;
case DIVIDE:
result = operand1 / operand2;
break;
case PLUS:
result = operand1 + operand2;
break;
case MINUS:
result = operand1 - operand2;
break;
}
stack.push(new Node(String.valueOf(result)));
}
}
return result;
}
}
import java.util.Scanner;
public class Test_Calculator {
public static void main(String[] args) {
Calculator c = new Calculator();
Scanner sc = new Scanner(System.in);
String infixExpression, postfixExpression;
double result = 0.0;
// 수식을 입력 받는다.
System.out.println("Enter Infix Expression : ");
infixExpression = sc.nextLine();
// 중위 표 기식 -> 후위 표기식
postfixExpression = c.getPostfix(infixExpression);
System.out.println("Infix : " + infixExpression);
System.out.println("Postfix : " + postfixExpression);
// 계산
result = c.calculate(postfixExpression);
System.out.println("Calculation Result : " + result);
}
}
결과)
Enter Infix Expression :
1+3.334/(4.28*(110-7729))
Infix : 1+3.334/(4.28*(110-7729))
Postfix : 1 3.334 4.28 110 7729 -*/+
Calculation Result : 0.9998977592909021
댓글 없음:
댓글 쓰기