위 예시에서 후위 표기법에서 나누기(/) 연산자가 더하기(+) 연산자보다 앞에 있으므로 나누기 연산부터 진행 후 더하기 연산을 한다는 것을 알 수 있음
연산자의 우선순위에 대해 알 필요가 없음 - 연산자의 배치 순서에 따라 연산 순서가 결정됨 - 위 같은 특성 때문에 소괄호에 대한 처리도 불필요함
소괄호가 없는 중위표기법에서 후위 표기법으로 변경하는 방법
예시) 중위표현식 : 5+2/7
숫자는 그대로 표현한다.
연산자는 스택에 저장한다.
스택에 연산자가 있을 경우 우선순위를 비교한다. 3-1. 새로 추가할 연산자의 우선순위가 더 높을 경우 스택에 저장한다. 3-2. 새로 추가할 연산자의 우선순위가 더 낮거나 같을경우 스택에 있는 우선순위가 높은 연산자를 빼서 표현하고, 새로운 연산자는 스택에 저장한다.
위 방법을 반복하며 더 이상 남은 중위 표현식이 없을 경우 스택에 저장된 연산자들을 모두 빼서 표현한다.
중위 표현식
후위 표현식
스택
번호
5+2/7
+2/7
5
방법 1
2/7
5
+
방법 2
/7
52
+
방법 1
7
52
/ +
방법 3-1
527
/ +
방법 1
527/+
방법 4
소괄호가 있는 중위 표현식을 후위 표현식으로 변경하는 방법
( ) 연산자는 우선순위가 다른 연산자들 보다 낮다고 가정 - 어디까지 괄호로 묶여 있는 것인지 판단하기 위해 필요
( 연산자 내부의 수직은 ) 연산자를 만날때까지 기존 후위 표기법과 방식이 동일
) 연산자가 나오면 스택에 저장된 모든 연산자를 표현 - ( ) 연산자는 표현하지 않음
1번부터 반복
예시) 중위 표현식 : (1+2*3)/4
중위 표현식
후위 표현식
스택
(1+2*3)/4
1+2*3)/4
(
+2*3)/4
1
(
2*3)/4
1
+ (
*3)/4
12
+ (
3)/4
12
* + (
)/4
123
* + (
/4
123
) * + (
/4
123*+
4
123*+
/
123*+4
/
123*+4/
소괄호가 있는 중위표기법을 후위 표기법으로 변경하는 기능 구현
기존에 직접 구현한 LinkedListStack을 이용 (java 내부에서 사용하는 Stack 사용해도 무방)
연산자 우선순위를 반환하는 메소드 작성
// 연산자 우선순위 반환
public static int getOpPriority(char c){
switch (c) {
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
default:
return -1;
}
}
연산자 우선순위를 비교하는 메소드 작성
// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우
if (stackOpPriority < curOpPriority){
return 1;
}
// 우선순위가 같은 경우
else if (stackOpPriority == curOpPriority){
return 0;
}
// 스택의 우선순위가 더 높은 경우
else {
return -1;
}
}
후위 표기법으로 변경하는 메소드 작성
public static String convPostfix(String infix){
char c = ' ';
Stack opStack = new LinkedListStack();
StringBuilder sb = new StringBuilder();
for(int i=0; i<infix.length(); i++){
c = infix.charAt(i);
// 숫자이면 표현
if (Character.isDigit(c)){
sb.append(c);
}
// 연산자 스택이 비어있을 경우 값 push
else if (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로
if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우
// 스택에 저장된 모든 연산자를 반환
else if (c == ')'){
char check = ' ';
while(true) {
check = (char) opStack.pop();
if (check == '(') {
break;
}
else {
sb.append(check);
}
}
continue;
}
// 현재 연산자의 우선순위가 더 높은 경우
// 스택에 연산자 저장
if (compareOp((char)opStack.peek(), c) > 0){
opStack.push(c);
}
// 현재 연산자의 우선순위가 더 낮거나 같은 경우
// 스택에 있는 우선순위가 높은 연산자를 빼서 표현
else {
while(!opStack.isEmpty()){
if (compareOp((char)opStack.peek(), c) <= 0){
sb.append(opStack.pop());
}
else {
break;
}
}
opStack.push(c);
}
}
}
char check = ' ';
while(!opStack.isEmpty()) {
check = (char) opStack.pop();
if (check != '(') {
sb.append(check);
}
}
return sb.toString();
}
후위 표기법 계산
public static double postfixCalculate(String postfix){
Stack stack = new LinkedListStack();
char c = ' ';
double op1 = 0;
double op2 = 0;
for(int i=0; i<postfix.length(); i++){
c = postfix.charAt(i);
// 숫자인 경우 스택에 저장
if (Character.isDigit(c)){
stack.push(c);
}
// 연산자인 경우 계산 후 스택에 저장
else {
op2 = Double.valueOf(stack.pop().toString());
op1 = Double.valueOf(stack.pop().toString());
switch (c){
// op2에 먼저 pop한 이유는 후위 표기법으로 변환할 때 순서가 바뀌기 때문
// ex) 3+2 => 스택에 저장 시 3, 2 순으로 저장되는데 스택은 마지막에 push한
// 데이터가 가장 위에 있으므로
case '+':
stack.push(op1 + op2);
break;
case '-':
stack.push(op1 - op2);
break;
case '*':
stack.push(op1 * op2);
break;
case '/':
stack.push(op1 / op2);
break;
}
}
}
return Double.valueOf(stack.pop().toString());
}
전체 소스코드
package Stack;
import Stack.Stack;
import Stack.LinkedList.LinkedListStack;
public class PostfixNotation {
public static void main(String[] args) {
String infix = "(1+2*3)/4";
String postfix = convPostfix(infix);
System.out.println(postfix);
System.out.println(postfixCalculate(postfix));
}
public static double postfixCalculate(String postfix){
Stack stack = new LinkedListStack();
char c = ' ';
double op1 = 0;
double op2 = 0;
for(int i=0; i<postfix.length(); i++){
c = postfix.charAt(i);
// 숫자인 경우 스택에 저장
if (Character.isDigit(c)){
stack.push(c);
}
// 연산자인 경우 계산 후 스택에 저장
else {
op2 = Double.valueOf(stack.pop().toString());
op1 = Double.valueOf(stack.pop().toString());
switch (c){
// op2에 먼저 pop한 이유는 후위 표기법으로 변환할 때 순서가 바뀌기 때문
// ex) 3+2 => 스택에 저장 시 3, 2 순으로 저장되는데 스택은 마지막에 push한
// 데이터가 가장 위에 있으므로
case '+':
stack.push(op1 + op2);
break;
case '-':
stack.push(op1 - op2);
break;
case '*':
stack.push(op1 * op2);
break;
case '/':
stack.push(op1 / op2);
break;
}
}
}
return Double.valueOf(stack.pop().toString());
}
public static String convPostfix(String infix){
char c = ' ';
Stack opStack = new LinkedListStack();
StringBuilder sb = new StringBuilder();
for(int i=0; i<infix.length(); i++){
c = infix.charAt(i);
// 숫자이면 표현
if (Character.isDigit(c)){
sb.append(c);
}
// 연산자 스택이 비어있을 경우 값 push
else if (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로
if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우
// 스택에 저장된 모든 연산자를 반환
else if (c == ')'){
char check = ' ';
while(true) {
check = (char) opStack.pop();
if (check == '(') {
break;
}
else {
sb.append(check);
}
}
continue;
}
// 현재 연산자의 우선순위가 더 높은 경우
// 스택에 연산자 저장
if (compareOp((char)opStack.peek(), c) > 0){
opStack.push(c);
}
// 현재 연산자의 우선순위가 더 낮거나 같은 경우
// 스택에 있는 우선순위가 높은 연산자를 빼서 표현
else {
while(!opStack.isEmpty()){
if (compareOp((char)opStack.peek(), c) <= 0){
sb.append(opStack.pop());
}
else {
break;
}
}
opStack.push(c);
}
}
}
char check = ' ';
while(!opStack.isEmpty()) {
check = (char) opStack.pop();
if (check != '(') {
sb.append(check);
}
}
return sb.toString();
}
// 연산자 우선순위 반환
public static int getOpPriority(char c){
switch (c) {
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
default:
return -1;
}
}
// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우
if (stackOpPriority < curOpPriority){
return 1;
}
// 우선순위가 같은 경우
else if (stackOpPriority == curOpPriority){
return 0;
}
// 스택의 우선순위가 더 높은 경우
else {
return -1;
}
}
}
결과 전위 표기법 : (1+2*3)/4
전위 표기법 : ((4+2)/4)-(3+2/(7*5))
2자리 이상의 숫자를 연산하려면 List와 StringBuilder로 구현 가능 StringBuilder를 이용해 문자가 나올 때까지 반복하고, 연산자가 나올 경우 숫자를 리스트에 저장하는 방식으로 구현 가능
