# Javascript/Algorithm : 전위/중위/후위 표기법

- Author: @laetipark
- Published: 2024-06-07
- Updated: 2024-06-07
- Source: http://blex.me/@laetipark/javascriptalgorithm-%EC%A0%84%EC%9C%84%EC%A4%91%EC%9C%84%ED%9B%84%EC%9C%84-%ED%91%9C%EA%B8%B0%EB%B2%95
- Tags: javascript, 알고리즘, 전위표기법, 후위표기법, 중위표기법, 계산기

---

### 개요
![](https://static.blex.me/images/content/2024/6/7/20246713_4hl6vbxmHHZyjgVs3Gxk.png)

회사에서 간단한 **실습 과제**로 `회사 솔루션의 에디터 내 계산기 기능`을 구현하는 것이 주어졌다.
그래서 `전위`, `중위`, `후위 표기법`에 대해 다시 공부하면서, `후위 표기법을 통한 계산`으로 구현한 `Javascript 코드`를 작성해보았다.

### 중위 표기법
- **중위 표기법(infix)** : `피연산자` 사이 `연산자`가 있는 형태로 일반적으로 사용하는 수식 표기법이다. 괄호와 연산자 우선순위를 고려한 다음 순서대로 연산이 이루어진다.
![](https://static.blex.me/images/content/2024/6/7/20246715_ofXwbEQIudSMeSNraEAE.png)  
`컴퓨터는 왼쪽부터 수식을 하나씩 읽어가기 때문`에, 우선순위가 있는 `중위 표기법`으로 구현하기 어려움이 있다. 그래서 `전위 표기법`, `후위 표기법`으로 변환한 후에 계산을 진행한다.

### 전위 표기법
- **전위 표기법(prefix)** : `연산자`를 먼저, `피연산자`를 나중에 표기하는 방식
![](https://static.blex.me/images/content/2024/6/7/20246717_fXQXR2caFgzwJDmW313z.png)
- 중위 표기법에서 전위 표기법 변환 (중위 표기법 : `1+2/3*(4+5)`)
	1. 연산자 우선순위에 맞게 소괄호로 묶는다. `(1+((2/3)*(4+5)))`
	2. 괄호 안에 있는 연산자들을 앞으로 옮긴다. `(+1(/*(23)+(45)))`
	3. 괄호들을 모두 없애준다. `+1/*23+45`


### 후위 표기법
- **후위 표기법(postfix)** : `피연산자`를 먼저, `연산자`를 나중에 표기하는 방식
![](https://static.blex.me/images/content/2024/6/7/20246717_jz3Pd0UMvRHepW6PKjJ6.png)
- 중위 표기법에서 후위 표기법 변환 (중위 표기법 : `1+2/3*(4+5)`)
	1. 연산자 우선순위에 맞게 소괄호로 묶는다. `(1+((2/3)*(4+5)))`
	2. 괄호 안에 있는 연산자들을 뒤로 옮긴다. `(1((23)/(45))+*+)`
	3. 괄호들을 모두 없애준다. `123/45+*+`

- `스택`을 이용한 중위 표기법에서 후위 표기법 변환 및 계산
![](https://static.blex.me/images/content/2024/6/8/2024680_Kz672o0wi5d8vRxTvMRu.png)
	- **피연산자**는 `output`에, **연산자**는 `operator stack(연산자 스택)`에 `push`
	- **탐색한 연산자**가 **operator stack top에 있는 연산자**보다 우선순위가 같거나 낮은지 확인
	- 우선순위가 같거나 낮다면 **operator stack top에 있는 연산자**를 `pop`하여 `output`에 `push`, `operator stack`에 **탐색한 연산자**를 `push`하는 방식
	- 후위 표기법 계산은 왼쪽부터 `stack`에 쌓으면서 **연산자**가 탐색되면, `stack`에 쌓여있는 **두 개의 피연산자**를 `pop`하여 해당 연산 진행한 후 다시 `stack`에 `push`하는 방식
		- `연산1(2/3)` => `연산2(4+5)` => `연산3(연산1*연산2)` => `연산4(연산3+1)`

##### 중위 표기법을 후위 표기법으로 변환 코드
```typescript
const infix = `["1", "+", "2",  "/", "3", "*", "(", "4", "+", "5", ")"]`; // 중위 표기법

// 중위 표기법을 후위 표기법으로 전환
let output = [];
let operatorStack = [];
let operators = {
  "+": 1,
  "‑": 1,
  "*": 2,
  "/": 2,
  "%": 2,
  "^": 3, // 제곱 연산자
  "=": 0,
};

for (let i = 0; i < infix.length; i++) {
  let token = infix[i];

  if (!isNaN(Number(token || NaN))) { // 피연산자(숫자)인 경우 output에 push
    output.push(token);
  } else if (token in operators) { // 연산자인 경우
    while (
      operatorStack.length > 0 &&
      operators[operatorStack[operatorStack.length - 1]] >=
        operators[token] &&
      operatorStack[operatorStack.length - 1] !== "("
    ) { // operatorStack top에 연산자 우선순위가 token보다 높은 경우 pop하여 output에 push
      output.push(operatorStack.pop());
    }
    operatorStack.push(token); // operatorStack에 push
  } else if (token === "(") { // 여는 괄호인 경우 operatorStack에 push
    operatorStack.push(token);
  } else if (token === ")") { // 닫는 괄호인 경우 여는 괄호가 나오거나 operatorStack가 비워질 때까지 operatorStack에서 pop 후 output에 push
    while (
      operatorStack.length > 0 &&
      operatorStack[operatorStack.length - 1] !== "("
    ) {
      output.push(operatorStack.pop());
    }
    operatorStack.pop();
  }
}

while (operatorStack.length > 0) {  // operatorStack에 남아있는 연산자들을 output에 push
  output.push(operatorStack.pop());
}
```

##### 후위 표기법 계산 코드
```typescript
for (let i = 0; i < res.length; i++) {
  let token = res[i];
  if (!isNaN(Number(token))) { // 피연산자(숫자)인 경우 stack에 push
    stack.push(Number(token));
  } else { // 연산자인 경우 stack에 있는 두 개의 수를 pop하여, 해당 연산 수행 후 stack에 다시 push
    let operand2 = stack.pop();
    let operand1 = stack.pop();

    switch (token) {
      case "+":
        stack.push(operand1 + operand2);
        break;
      case "‑":
        stack.push(operand1 - operand2);
        break;
      case "*":
        stack.push(operand1 * operand2);
        break;
      case "/":
        stack.push(operand1 / operand2);
        break;
      case "%":
        stack.push(operand1 % operand2);
        break;
      case "^": // 제곱 연산자
        stack.push(operand1 ** operand2);
        break;
    }
  }
}

const answer = stack.pop(); // 후위 표기법 계산 결과
```