[후위표기법] 후위표기식으로 계산기 만들기 (html, js 이용) :: 개념에서 구현까지

By 희은w

2020. 12. 21. 00:00

후위표기법으로 계산기 만들기

계산기 관련 외주가 들어와서 해보던 중, 예전에 배웠던 후위표기법을 사용해야했다. 그런데 기억이 안나서 검색 없이 혼자 구현하려다 보니 너무 어려웠다... 검색해보니까 stack을 이용해서 후위표기법을 만드는 간단한 방법이 나와있어서 까먹지 않기 위해 기록한다.

후위 표기법

수식 트리

후위 표기법이란 계산식에서 계산을 위해 사용하는 표기법이다. 예제와 함께 살펴보자.

수식 : 9x3+1-3%3

수식이 주어졌을 때 비연산자와 연산자로 나눈 후, 각 항목을 하나의 노드라고 생각하면 트리 형태로 만들 수 있다.

이러한 트리는 수식을 트리라는 자료구조로 만든 것이니 수식트리, 즉 Expression Tree라고 불린다.

트리 순회와 표기법

트리를 순회하는 방식에는 prefix(전위), infix(중위), postfix(후위)가 있는데,

[트리 링크] 참조

위에서 나온 일반적으로 우리가 사용하는 수식은 중위순회로 수식트리를 순회하여 나온 중위표기법이다.

이를 컴퓨터에서 계산하기 좋은 방식으로 바꿔주려면 후위 순회를 통해 후위표기법을 만들어야한다.

후위순회는 다음과 같은 방식으로 진행되며, 결과로 나오는 수식은 다음과 같다.

수식 : 93x1+33%-

후위 표기식 만들기

후위표기식을 만들고 계산하는 법을 배웠다. 그런데 꼭 트리로 만들어서 후위표기식을 작성해야할까?

본인도 이렇게 후위표기식을 만들려다가 간단한 방법이 있었던 것 같아 검색을 해보았다.

간단한 방법은 또 stack을 이용하는 것이다. 규칙은 다음과 같다.

비연산자(숫자)가 나오면 stack에 집어넣는다(push).
연산자가 나오면
1. operator stack에 연산자가 없으면 집어넣는다(push).
2. operator stack에 있는 연산자가 해당 연산자보다 우선순위가 높거나 같다면 operator stack에 있는 연산자를 빼서(pop) stack에 집어넣고(push), 현재 연산자를 operator stack에 넣는다(push).
3. operator stack에 있는 연산자가 해당 연산자보다 우선순위가 낮다면 operator stack에 넣는다(push).

위에서 언급한 연산자의 우선순위는 +, - < x, % < (, )이다.

예시 수식을 가지고 후위표기식을 만들어보자.

수식 : 9x3+1-3%3

우선순위가 더 높은 연산자가 스택에 있으면 빼고, 해당 연산자를 스택에 집어넣는다.

결과에 있는 값들을 차례로 빼내면 후위표기식이다.

후위 표기식 계산

그렇다면 주어진 후위표기법 수식에 대해서는 어떻게 계산할 수 있을까? 규칙은 다음과 같다.

비연산자(숫자)가 나오면 number stack에 집어넣는다(push).
[stack 링크] 참조
연산자가 나오면
1. number stack에서 2개의 숫자를 꺼낸다(pop).
2. 2개의 숫자를 연산자를 이용해 계산한다.
3. 결과로 나온 숫자를 다시 number stack에 집어넣는다(push).

예시로 주어진 수식을 통해 자세한 과정을 살펴보면 다음과 같다.

연산자가 나오면, 숫자 스택에서 2개의 숫자를 꺼내서 계산한다. 그리고 계산 결과를 다시 숫자 스택에 넣는다.

이러한 계산 방식을 반복한다.

결과는 27이다.

우리에게 익숙한 중위표기법으로 된 수식을 직접 풀어보면

수식 : (9x3)+1-(3%3) = 27+1-1 = 27

정답이다.

계산기 만들기

코드는 다음과 같다.

<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>계산기 만들기</title>
<link rel="stylesheet" href="hw04.css" />
<script type="text/javascript" src="hw04.js"></script>

</head>

<body>
<h3>계산기 만들기</h3>
<hr>

<table>
    <tr>
        <td colspan="4"><input type="text" id="lcd" value="0" size="50"></td>
    </tr>
    <tr>
        <td><input type="button" value="BACK" onclick="backward()"></td>
        <td><input type="button" value="CE" onclick="clearLcd()"></td>
        <td><input type="button" value="C" onclick="clearLcd();"></td>
        <td><input type="button" value="=" onclick="calculate()"></td>
    </tr>
    <tr>
        <td><input type="button" onclick="addInput(7)" value=7></td>
        <td><input type="button" onclick="addInput(8)" value=8></td>
        <td><input type="button" onclick="addInput(9)" value=9></td>
        <td><input type="button" onclick="addInput('+')" value='+'></td>
    </tr>
    <tr>
        <td><input type="button" onclick="addInput(4)" value=4></td>
        <td><input type="button" onclick="addInput(5)" value=5></td>
        <td><input type="button" onclick="addInput(6)" value=6></td>
        <td><input type="button" onclick="addInput('-')" value='-'></td>
    </tr>
    <tr>
        <td><input type="button" onclick="addInput(1)" value=1></td>
        <td><input type="button" onclick="addInput(2)" value=2></td>
        <td><input type="button" onclick="addInput(3)" value=3></td>
        <td><input type="button" onclick="addInput('x')" value='x'></td>
    </tr>
    <tr>
        <td><input type="button" value='NONE'></td>
        <td><input type="button" onclick="addInput(0)" value=0></td>
        <td><input type="button" value='NONE'></td>
        <td><input type="button" onclick="addInput('%')" value='%'></td>
    </tr>
<table>
</body>
</html>

html 구성은 위와 같다.

계산 결과와 과정은 id가 lcd인 text input에 나타난다.
연산자나 비연산자 버튼을 누르면 addInput 함수가 호출되도록 하였다. addInput 함수는 lcd에 누른 버튼을 그대로 출력해주는 역할을 한다.
C나 CE를 누르면 lcd가 0으로 초기화 된다.
Back 버튼을 누르면 lcd에 출력된 수식에서 마지막 글자가 지워진다.
= 버튼을 누르면 lcd에 출력된 수식의 결과가 계산되어 lcd에 출력된다.

function addInput(b) {// 숫자나 기호가 눌려지면 그대로 화면에 출력해주는 함수
    var lcd = document.getElementById('lcd');
    lcd.value = lcd.value=="0"?"":lcd.value; // 값이 0이면 없애고 숫자 및 기호 추가
    lcd.value += typeof(b)==Number?b.toString():b; // 숫자면 string으로 변환
}

function backward() { //back 버튼에 대한 처리 함수
    var lcd = document.getElementById('lcd');
    lcd.value = lcd.value.substring(0, lcd.value.length-1);
    lcd.value = lcd.value==""?"0":lcd.value; // 값이 없으면 0 노출
}
function calculate() { // "="가 눌러진 경우. 계산하고 결과 출력
    var lcd = document.getElementById('lcd');
    var arr = [];
    var value = 0;
    var stack = [];
    for(var char of lcd.value){ 
        // 배열에 숫자 / 문자 구분해서 넣기
        // 후위 연산 순서로 넣기
        if(!isNaN(char)){ // 숫자이면
            value = 10*value+Number(char);
        }else{ // 문자이면
            arr.push(value);
            const tmp = stack.pop();
            if(tmp==undefined){ // stack이 비어있으면
                stack.push(char);
            }else{
                if(operPriority(tmp,char)){
                    // stack의 연산자가 더 우선순위가 높거나 같으면 stack에서 빼고 넣기
                    arr.push(tmp); stack.push(char);
                } else{ // 낮으면 stack에 쌓기
                    stack.push(tmp); stack.push(char);
                }
            }
            value=0;
        }
    }
    arr.push(value);
    let pop_element = stack.pop(); // stack에 있는 연산자 다 빼기
    while(pop_element!=undefined){
        arr.push(pop_element);
        pop_element = stack.pop();
    }

    // 계산
    var value=[];
    for(var char of arr){
        if(!isNaN(char)){ // 숫자이면
            value.push(char);
        } else{ // 문자이면
            const v1 = value.pop();
            const v2 = value.pop();
            switch(char){
                case "+":
                    value.push(v2+v1);
                    break;
                case "-":
                    value.push(v2-v1);
                    break;
                case "x":
                    value.push(v2*v1);
                    break;
                case "%":
                    if(v2==0)
                        alert("0으로 나눌수 없습니다.");
                    else
                        value.push(v2/v1);
                    break;
            }
        }
        const tmp = value.pop();
        value.push(tmp);
    }
    lcd.value=value.pop();
}

function operPriority(oper1, oper2){
    // oper2의 우선순위가 같거나 크면 true 반환
    switch(oper1){
        case "+":
        case "-":
            if(oper2=="x" || oper2 =="%")
                return false;
            return true;
        case "x":
        case "%":
            return true;
    }
}

function clearLcd() {  // "CE", "C"가 눌러진 경우, lcd 클리어 
    var lcd = document.getElementById("lcd");
    lcd.value = "0";
}

js 구성은 위와 같다.

연산자의 우선순위를 계산해주는 operPriority 함수를 후위표기식을 만들 때 사용하였다.
수식을 계산하는 calculate 함수는
- 후위표기식을 만들고
- 표기식을 계산하는 역할을 한다.

저작자표시 비영리 변경금지

Notice

Category

Recent Post

Popular Post

Comment

Tags

Visitor Counter