[알고리즘] Stack - 수식의 표현(수정)

프로그래머스 데브코스 진행 중 배우게 된 알고리즘 관련 내용을 정리해보았다.

출처 : 프로그래머스 어서와, 자료구조와 알고리즘은 처음이지?

 

문제 설명

'문자열'로 주어진 수식이 있다. 이 수식의 값을 계산할 수 있을까?

 

중위 표현식, 후위 표현식

중위 표현식이란, 우리가 흔히 표현하는 수식의 형태를 뜻한다.

예시) (A + B) * (C + D)

후위 표현식이란, 연산자를 뒤에 표현하는 방법이다. 위의 식을 후위 표현식으로 바꾸면 다음과 같다.

예시) (A + B) * (C + D) -> AB+CD+*

 

1단계) 중위 표현식을 후위 표현식으로 변경

우리가 사용하는 중위 표현식으로는 수식의 값을 올바르게 계산하기가 어렵다.

그 이유는 다음 두 가지가 존재한다.

- 사칙연산에 우선순위가 존재한다. 또한 우선순위가 모두 다른 것이 아니라 같은 것들이 존재하는데 같은 것들은 좌측부터 계산해야 하기에, 중위 표현식 상태로는 알고리즘을 짜기가 어렵다.

- 괄호의 존재가 우선순위를 뒤바꿔 버린다. 

하지만 후위 표현식을 사용할 경우, 연산을 언제 해야하는지가 조금 더 명백해진다. 후위 표현식을 보고 어떻게 계산을 할 수 있는지는 다음 단계에서 확인하기로 하고, 일단은 중위 표현식을 후위 표현식으로 바꾸는 방법에 대해 알아보자.

 

알고리즘

알고리즘에는 Stack을 사용할 것이다.

우선순위에 따라, 기호를 올바르게 빼내줘야 하기에 Stack이 적합하다.

- 주어진 중위 표현식을 순차적으로 읽는다.
- 만일, 숫자(문자)라면 후위 표현식이 될 문자열에 더해준다.
- 만일, 사칙연산 기호가 나온다면 
  - 최초이거나 Stack이 비어있을 경우 연산자를 Stack에 삽입하다.
  - Stack이 비어있지 않을 경우, Stack 최상단의 연산자와 읽은 연산자의 우선순위를 비교한다.
    - 만일 스택의 연산자의 우선순위가 더 높거나 같다면(같을 경우 좌측부터 읽으니까), 
      스택에서 pop을 하며 후위 표현식에 더한다. 스택을 우선순위가 더 낮은 연산자가 나올때 까지 비운 후 읽은 연산자를 push한다.
    - 스택의 연산자의 우선순위가 더 낮다면, 읽은 연산자를 스택에 push한다.
 - 괄호가 나온다면, 우선은 여는 괄호를 스택에 넣는다.
   - 여는 괄호 때문에 다른 앞에 있던 기호를 날려먹어서는 안된다. 여는 괄호의 우선순위는 최하순위이다.
   - 닫는 괄호를 만난다면, Stack에 쌓인 거를 pop해가면서 후위 표현식 문자열에 더한다.
      그러다 여는 괄호를 만난다면, pop하는 것을 중단하고 여는 괄호까지만 날려버린다.
      물론 당연히, 여는 괄호는 후위 표현식에 더해서는 안된다.
 - 이렇게 수식의 마지막까지 도착하면  Stack에 남은 것을 싹 다 pop해서 후위 표현식에 더해준다.

복잡하니까, 그림을 통해 과정을 확인해보자.

코드작성

위의 내용을 순차적으로 작성해야 한다. 특이사항은 다음과 같다.

1. Stack이 비어있는 상황에 주의해야 한다.
2. 우선 순위 확인을 위해 stack에서 peek을 활용하여 pop하기 전에 우선순위를 판단하자.
3. Stack.peek의 우선순위가 더 높아서 pop시킬때 우선순위가 높을때까지만 Stack을 비워줘야 하는 것을 잊지 말자.
4. 마지막 단계에서 스택을 비워줘야 하는것도 잊어서는 안 된다.

어제는 저 부분을 착각하였는데, 바로 반례를 발견하여 우선순위에 대해 고쳐야 한다.

위의 사항에 주의하여 코드를 작성하면 다음과 같다.

def solution(S):
    # 수식의 유효성은 검사하지 않으며
    # 숫자 대신에 문자를 사용한다고 가정한다.
    opStack = ArrayStack()
    answer = ''
    
    for c in S:
        if c not in '()+-*/': 
            answer += c
        elif c == '(':
            opStack.push(c)
        elif c == ')':
            while not opStack.isEmpty():
                pops = opStack.pop()
                if pops == "(":  # 그만 비워야 하는 시점
                    break
                else:
                    answer += pops
        else:
            if not opStack.isEmpty():
                while not opStack.isEmpty():  # 비지 않을때까지만
                    if prec[opStack.peek()] >= prec[c]: # 우선순위가 더 높으면
                        answer += opStack.pop()
                    else: # 낮으면 즉시 중단하라.
                        break
                opStack.push(c)

            else:  # 스택이 애초에 비어서 기호를 추가한다.
                opStack.push(c)
    
    while not opStack.isEmpty():  # 최종적으로 스택에 남은 기호를 더한다.
        answer += opStack.pop()

 

2단계) 후위 표현식을 바탕으로 값 계산하기

이제 후위 표현식으로 변경했으니, 값으로 계산하는 방법을 알아보자.

수식을 숫자와 기호로 분해하기

1단계의 가정은 숫자 대신에 문자를 사용했다는 점에서 간단했으나, 실제 계산을 위해서는 숫자로 된 식을 문자로 바꿔야 할 것이다.  프로그래머스 과정에서는 해당 코드를 제공하였다. 숫자를 만날 경우 flag를 활용하여 기호를 만날 때 까지 숫자의 값을 계속 저장하는 방식으로 코드를 만들었고, 실제 결과는 숫자와 기호가 섞여있는 list를 반환하게 만들어져 있다. 이 함수를 확인해보면 다음과 같다. 물론 이는 중위표현식을 기준으로 만들어져 있다. 

따라서 얻은 List를 바탕으로 다시 수식을 후위 표현식으로 바꿔주어야 겠으나 위의 코드와 차이가 거의 없으므로 해당 코드는 생략하고자 한다. (사실 리스트로만 바꾸면 된다..)

def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
        tokens.append(val)

    return tokens

 

후위 표현식을 바탕으로 값 계산하기

후위 표현식을 바탕으로 수식의 값을 계산하는 방법은 간단하다.

1. 숫자를 담는 Stack을 만든다.
2. 숫자를 만나면 push를 한다.
3. 기호를 만나면 Stack 에서 숫자 2개를 pop하여 해당 기호로 연산 후 그 값만 다시 push 한다.
4. 마지막 까지 읽으면, Stack에는 1개의 숫자만 남아 있다. 해당 값을 pop하면 된다.

해당 내용을 코드로 작성하면 다음과 같다.

def postfixEval(tokenList):
    numStack = ArrayStack()
    for c in tokenList:
        if str(c) not in ["(", ")", "+", "-", "*", "/"]:
            numStack.push(c)
        else:
            y = numStack.pop()
            x = numStack.pop()
            
            if c == "+":
                numStack.push(x + y)
            elif c == "-":
                numStack.push(x - y)
            elif c == "*":
                numStack.push(x * y)
            elif c == "/":
                numStack.push(x / y)
    return numStack.pop()