기존 숫자 2개와 연산 기호를 받는 계산기에서 수식을 받아서 연산 처리를 하는 방식으로 바꿔보려고 한다. 바꾸는 과정에서 알고리즘을 제대로 숙지하지 못해 기대한 결과와 다른 결과를 많이 보게 돼서 숫자를 변환하는 과정을 먼저 보고 이후 코드에 실제로 대입해서 만들어 봤다.

Step 1. 중위 표기법을 후위 표기법으로 변경

1-1. 표기법을 바꾸는 이유

먼저 표기법을 바꿔야 하는 이유를 간단히 살펴보자.

중위 표기법이란 우리가 흔히 사용하는 피연산자 사이에 연산자가 들어가는 방식으로 1 + 2 - 3 * 4 와 같은 방식을 말한다. 하지만 중위 표기법을 이용해서 작성된 수식에는 연산 순서에 대한 정보가 없다. 따라서 연산자가 자리한 위치만 보고서도 판단할 수 있는 전위 표기법이나 후위 표기법으로 변환해야 한다.

1-2. 중위 표기법을 후위 표기법으로 바꾸는 방법

중위 표기법을 후위 표기법으로 바꾸는 방법은 다음과 같다.

괄호가 없는 수식의 경우

1. 피연산자의 경우 바로 적는다.
2. 연산자의 경우 Stack 안에 넣는다.
   a. 만약 Stack에 저장된 연산자의 우선순위가 새로 들어오는 연산자보다 같거나 높을 경우 연산자를 밖으로 빼내고, 새로 들어오는 연산자를 Stack에 저장한다.
3. 위의 방법을 토대로 정리하고, Stack에 남은 연산자를 뒤에 붙여서 마무리한다.

괄호가 있는 수식의 경우

1. 피연산자의 경우 바로 적는다.
2. 연산자의 경우 Stack 안에 넣는다.
   a. 괄호는 왼쪽의 경우 Stack에 저장하고, 닫히기 전까지 같은 방식으로 진행한다. (단, 괄호는 우선순위를 비교하지 않고 그대로 저장)
   b. 만약 괄호가 닫히기 전에 Stack에 저장된 연산자의 우선순위가 새로 들어오는 연산자보다 같거나 높을 경우 연산자를 밖으로 빼내고, 새로 들어오는 연산자를 Stack에 저장한다.
   c. 오른쪽 괄호가 들어와서 닫힐 경우 오른쪽 괄호는 Stack에 넣지 않고 버리고, 왼쪽 괄호가 나올 때까지 연산자를 밖으로 빼내고 왼쪽 괄호가 나올 경우 버린다.
3. 위의 방법을 토대로 정리하고, Stack에 남은 연산자를 뒤에 붙여서 마무리한다.

괄호가 없는 수식을 변환할 경우

위의 방법을 토대로 중위 표기법으로 작성된 1 + 2 - 3 * 4를 후위 표기법으로 바꿔보자.

1. 1은 피연산자이므로 바로 작성한다.
   • result: 1
2. +는 연산자이므로 Stack에 넣는다.
   • result: 1
   • stack
     • 0: +
3. 2는 피연산자이므로 바로 작성한다.
   • result: 12
   • stack
     • 0: +
4. -는 연산자이므로 Stack에 넣는다. 이때 +와 -의 우선 순위가 동일하기 때문에 먼저 들어온 +를 제거하고, 결과에 작성한다.
   • result: 12+
   • stack
     • 0: -
5. 3는 피연산자이므로 바로 작성한다.
   • result: 12+3
   • stack
     • 0: -
6. *는 연산자이므로 Stack에 넣는다.
   • result: 12+3
   • stack
     • 1: *
     • 0: -
7. 4는 피연산자이므로 바로 작성한다.
   • result: 12+34
   • stack
     • 1: *
     • 0: -
8. Stack에 남은 연산자를 마지막에 붙여서 마무리한다.
   • result: 12+34*-

따라서 결과는 12+34*-가 된다.

괄호가 있는 수식을 변환할 경우

위의 방법을 토대로 중위 표기법으로 작성된 1 + (2 - 3) * 4를 후위 표기법으로 바꿔보자.

1. 1은 피연산자이므로 바로 작성한다.
   • result: 1
2. +는 연산자이므로 Stack에 넣는다.
   • result: 1
   • stack
     • 0: +
3. (는 괄호이므로 우선순위 비교 없이 바로 저장한다.
   • result: 1
   • stack
     • 1: (
     • 0: +
4. 2는 피연산자이므로 바로 작성한다.
   • result: 12
   • stack
     • 1: (
     • 0: +
5. -는 연산자이므로 Stack에 넣는다.
   • result: 12
   • stack
     • 2: -
     • 1: (
     • 0: +
6. 3은 피연산자이므로 바로 작성한다.
   • result: 123
   • stack
     • 2: -
     • 1: (
     • 0: +
7. 닫는 괄호인 )가 들어왔기 때문에 (과 )사이에 있는 모든 연산자를 순서에 맞게 꺼내서 작성한다.
   • result: 123-
   • stack
     • 0: +
8. *는 연산자이므로 Stack에 넣는다.
   • result: 123-
   • stack
     • 1: *
     • 0: +
9. 4는 피연산자이므로 바로 작성한다.
   • result: 123-4
   • stack
     • 1: *
     • 0: +
10. Stack에 남은 연산자를 마지막에 붙여서 마무리한다.
    • result: 123-4*+

Step 2. 후위 표기법을 토대로 연산

2-1. 후위 표기법 연산 방법

후위 표기법을 토대로 연산하는 방법은 다음과 같다.

후위 표기법 연산

1. 피연산자의 경우 Stack에 넣는다.
2. 연산자가 나올 경우 Stack에 저장된 피연산자 2개를 꺼내서 연산하고, Stack의 맨 위에 다시 넣는다. (순서가 헷갈릴 수 있으니 주의)
3. 위 방법을 반복해서 결과를 도출한다.

예시

위에서 변환한 두 수식을 연산 방법에 따라서 계산해보자.

1 + 2 - 3 * 4 연산하기

1 + 2 - 3 * 4를 변환한 결과는 1 2 + 3 4 * -이다.

1. 1은 피연산자이므로 Stack에 넣음
   • stack
     • 0: 1
2. 2은 피연산자이므로 Stack에 넣음
   • stack
     • 1: 2
     • 0: 1
3. +는 연산자이므로 Stack의 최상단 피연산자 2개를 꺼내서 연산 후 다시 Stack의 맨 위에 넣는다.
   • 1 + 2 = 3
   • stack
     • 0: 3
4. 3은 피연산자이므로 Stack에 넣음
   • stack
     • 1: 3
     • 0: 3
5. 4는 피연산자이므로 Stack에 넣음
   • stack
     • 2: 4
     • 1: 3
     • 0: 3
6. *는 연산자이므로 Stack의 최상단 피연산자 2개를 꺼내서 연산 후 다시 Stack의 맨 위에 넣는다.
   • 3 * 4 = 12
   • stack
     • 1: 12
     • 0: 3
7. -는 연산자이므로 Stack의 최상단 피연산자 2개를 꺼내서 연산 후 다시 Stack의 맨 위에 넣는다.
   • 3 - 12 = -9
   • stack
     • 0: -9
8. 결과 도출
   • result: -9

1 + (2 - 3) * 4 연산하기

1 + (2 - 3) * 4를 변환한 결과는 1 2 3 - 4 * +이다.

1. 1은 피연산자이므로 Stack에 넣음
   • stack
     • 0: 1
2. 2은 피연산자이므로 Stack에 넣음
   • stack
     • 1: 2
     • 0: 1
3. 3은 피연산자이므로 Stack에 넣음
   • stack
     • 2: 3
     • 1: 2
     • 0: 1
4. -는 연산자이므로 Stack의 최상단 피연산자 2개를 꺼내서 연산 후 다시 Stack의 맨 위에 넣는다.
   • 2 - 3 = -1
   • stack
     • 1: -1
     • 0: 1
5. 4는 피연산자이므로 Stack에 넣음
   • stack
     • 2: 4
     • 1: -1
     • 0: 1
6. *는 연산자이므로 Stack의 최상단 피연산자 2개를 꺼내서 연산 후 다시 Stack의 맨 위에 넣는다.
   • -1 * 4 = -4
   • stack
     • 1: -4
     • 0: 1
7. +는 연산자이므로 Stack의 최상단 피연산자 2개를 꺼내서 연산 후 다시 Stack의 맨 위에 넣는다.
   • 1 - 4 = -3
   • stack
     • 0: -3
8. 결과 도출
   • result: -3

이제 변환 및 연산하는 방법을 알았으니 다음엔 코드로 구현해보자.

References

• https://smhope.tistory.com/204 (계산기)
• https://settembre.tistory.com/271 (계산기)
• https://stackoverflow.com/questions/41813533/converting-string-to-number-in-java (String 값을 Number로 바꾸는 방법)
• https://stackoverflow.com/questions/2816715/branch-from-a-previous-commit-using-git (이전 커밋에서 브랜치 분기하는 방법)