스택의 응용 ( 수식의 후위 표기법 )

중위 표기법(infix notation)

• 연산자가 피연산자들의 사이에 위치
  ex) (A + B) * (C + D)

후위 표기법(postfix notation)

• 연산자가 피연산자들의 뒤에 위치
  ex) AB + CD + * ==> 괄호가 필요 없어짐

중위표현식 -> 후위표현식

• 중위 : A * B + C ==> 후위 ( A B 곱하기 + )
• 중위 : A + B * C ==> 후위 ( A B C 곱하기 + )

괄호의 처리

• 여는 괄호는 스택에 push
• 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop
• 연산자를 만났을 떄, 여는 괄호 너머까지 pop하지 않도록 여는 괄호의 우선순의는 가장 낮게 설정한다.

예제

[중위] (A + B) (C + D)
==> AB+CD+
[중위] (A + (B - C)) D
==> ABC -+D
[중위] A (B - (C + D))
==> ABCD +-

알고리즘의 설계

• 연산자의 우선순위 설정

prec = {
    '*':3,'/':3
    '+':2,'-':2,
    '(':1
    }

• 중위 표현식을 왼쪽부터 한 글자씩 읽어서 피연산자이면 그냥 출력
• '('이면 스택에 push
• ')'이면 '('이 나올 때까지 스택에서 pop, 출력
• 연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력
  그리고 이 연산자는 스택에 push
  스택에 남아있는 연산자는 모두 pop, 출력

코드의 구현 - 힌트

• 스택의 맨 위에 있는 연산자와의 우선순위 비교
  ( 스택에서 꺼내지 않고 비교만 해주기 위해서 스택의 peek() 연산 이용 )
• 스택에 남아있는 연산자 모두 pop()하는 순환문
  while not opStack.isEmpty(): 스택이 비어있지 않는 동안.

  def solution(S):
    opStack = ArrayStack()
    answer = ''
    
    ## S 전체 연산을 처음부터 반복하면서 push or pop
    for char in S :
        ## '('이면 스택에 push
        if char == '(':
            opStack.push(char)
        ## ')'이면 '('가 나올 때까지 pop, 출력
        elif char == ')' :
            while opStack.peek() != '(':
                answer += opStack.pop()
            opStack.pop()
            
        elif char in '+,-,*/':
            if opStack.isEmpty():
                opStack.push(char)
            else:
                while opStack.size() > 0:
                    ## dic을 활용해 숫자가 높은 연산자를 먼저 pop한다.
                    if prec[opStack.peek()] >= prec[char]:
                        answer += opStack.pop()
                    else:
                        break
                opStack.push(char)
                
        else :
            answer += char
        
    while not opStack.isEmpty() :
        answer += opStack.pop() 
    return answer

• 예시

for char in S :
    if char in prec :
        if opStack.isEmpty() :
            opStack.pop()
        elif char = '(' :
            opStack.push(char)
        elif prec[char] > prec[opStack.peek()]:
            opStack.push(char)
        elif prec[char] < prec[onStack.peek()]"
            opStack.push(char)
        else :
            opStack.push(char)
     elif char == ')':
         while opStack.peek() != '(':
             answer += opStack.pop()
         opStack.pop()
     else:
         answer += char
     
 while opStack.isEmpty() == False:
     answer += opStack.pop()
 return answer

- 예시

def solution(S):
    opStack = ArrayStack()
    answer = ''
    # 전체 수식을 순서대로 반복문에 넣어서 하나씩 비교 
    for ch in S:          
        # 하나씩 읽어서 '('이면 스택에 push
        if ch is '(':
            opStack.push(ch)
        # ')'이면 스택에서 pop을 해주는데 마무리 괄호라해서 수식이 끝난 것이 아닐 수 있기 때문에 스택이 비었는지 확인한 후 pop 한다.
        elif ch is ')':
            while not opStack.isEmpty():
                if opStack.peek() is '(':
                    opStack.pop()
                    break
                else:
                    answer += opStack.pop()
        elif ch in prec:
            if opStack.isEmpty():
                opStack.push(ch)
            # 만약 스택에 있는 연산자의 우선순위가 크다면 pop 우선순위가 작다면 다음 연산자는 스택에 push해준다.  
            else:
                if prec[opStack.peek()]>= prec[ch]:
                    answer += opStack.pop()
                opStack.push(ch)  
        # answer에 피연산자를 넣어준다.
        else:
            answer += ch  
    # 스택이 빌때까지 pop한다.
    while not opStack.isEmpty():
        answer += opStack.pop()
    return answer

- 다른 예시

for c in S:

피연산자를 isalpha로 확인해주었다.

    if c.isalpha():
        answer += c
    elif c == '(':
        opStack.push(c)
    elif c == ')':
        while opStack.peek() != '(':
            answer += opStack.pop()
        opStack.pop()
    else:
        if not opStack.isEmpty():
            while not opStack.isEmpty() and prec[c]<= prec[opStack.peek()]:
                answer+= opStack.pop()
            opStack.push(c)
        else:
            opStack.push(c)
while not opStack.isEmpty():
    answer+= opStack.pop()