후위 표기법 (Postfix Notation)

중위표기법 (infix notation) - 연산자가 피연산자들 사이에 위치

예) (a+b)*(c+d)

 

후위표기법 (postfix notation) - 연산자가 피연산자들의 뒤에 위치

예) ab+cd+*

 

 

[중위 표현식을 후위 표현식으로 변경하기 (feat.스택)]

a*b+c  => ab*c+

a+b*c =>abc*+

//문자는 그 순서 그대로, (피연산자1)(피연산자2)(연산종류) 이 형태 유지

 

1) 스택에 넣기

피연산자인 경우 바로 print

연산자는 stack 에 push

->우선순위가 더 높(거나같 - 먼저나온게 우선임)은게 들어있다면(지금 넣는 것보다 먼저 해야 하니까), pop 하고나서 push

->우선순위가 더 낮은게 들어있다면, 지금 있는 것보다 위에 있어야 하므로 push

수식의 끝까지 왔을 때 stack에 남아있는 연산자 그대로 pop

 

2) 괄호의 처리

 

여는 괄호를 스택에 push하고, 닫는 괄호를 만나면 여는 괄호가 나올 때 까지 stack 에 push된 연산자들을pop

 

괄호가 있는 식은 뒤에 있어도 우선순위가 앞에 있는(괄호가 없는) 식보다 우위이므로, 여는 괄호는 stack에 무엇이 있든 간 그 위에 push 되어야 한다. 즉, 우선순위가 스택내의 어떤 연산자보다 높다. 

 

 하지만, stack에 들어간 이후를 생각해 보자. 최소 닫는 괄호가 나오기 전까지 들어오는 모든 연산자들은 (의 위에 쌓여야 한다. 괄호가 닫혀야 그 연산이 끝난 것이므로 , 섣불리 연산자를 pop해선 안된다. 그러므로, 열린 괄호는 stack에 ㅡㄹ어간 이후엔 모든 연산자들중 우선순위가 가장 낮다. 

 

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

//과정 그리기

 

 

[ 알고리즘 설계 ]

 

연산자 우선 순위 및 알고리즘 흐름

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

 

중위 표현식을 한 글자씩 읽는다:
    피연산자면 바로 출력
    열린 괄호 '(' 면 바로 스택에 push 
     ')'면 '('을 만날때까지 pop, 출력
     연산자면 스택에서 높거나 같은 우선순위(우선순위가 같으면 나온 순서 기준이기 때문)를 pop, 출력하고 
     해당 연산자는 push //낮은 연산자가 있으면 바로 그 위에 push
스택에 남아있는 연산자를 모두 pop, 출력

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]
prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

def solution(S):
    opStack = ArrayStack()
    answer = ''
    for s in S:
        if s not in prec and s!=')': 
            answer+=s
        else: 
            if s=='(': 
                opStack.push(s)
                
            elif s==')': 
                while opStack.peek()!='(':
                    answer+=opStack.pop()
                opStack.pop()
            else: 
                while opStack.isEmpty()==False and prec[s]<=prec[opStack.peek()]:
                    answer+=opStack.pop()
                opStack.push(s)
                
    while not opStack.isEmpty():
        answer+=opStack.pop()
        
    return answer

 

 우선순위를 비교할땐 peek()을 이용하여 이를 꺼내지 않고 값만 받아온다.

또한, 스택에 남아있는 연산자를 모두 pop하기 위해선 while not opStack.isEmty() 순환문을 사용한다.

 

[ 후위 표기식의 계산 ]

"피연산자1-피연산자2-연산자" 관계 적용

=> 피연산자는 스택에 넣고, 연산자를 만나면 피연산자를 두개 꺼내서 계산한다.

     또한, 중간에 연산 결과를 스택에 저장한다.(괄호 대비) - 하나의 피연산자가 됨.

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

 

 

[ 알고리즘 설계 ]

후위 표현식 계산 과정 (토큰 별로)

후위 표현식을 계산하는 방법(토큰 별로)
 후위 표현식을 왼쪽부터 한 글자씩 읽어서:
    피연산자면 push()
    연산자면 스택에서 pop() 2회 -> 스택에 push
수식의 끝에 도달하면 하나 남은 스택 pop

 

전체적인 계산 순서

1. splitTokens() - 문자열 -> 토큰별로 분리 (숫자와 문자의 분리)

2. infixToPostifx() - 토큰을 infix에서 postfix 형태로 순서 바꾸기

3. postfixEval() - postfix 순의 토큰을 계산하기

 

splitTokens

 str형의 숫자는 int로 바꾸고, 연산자는 문자형 그대로 피연산자만 모아서 tokenList에 저장함.

 

def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c==' ':
            continue
        if c in '0123456789': #숫자가 몇번째 index까지 이어지는지 모르므로 valProcessing으로 진행상황 표시, val로 저장
            val = val * 10 + int(c)
            valProcessing = True
        else: #이제 숫자로된 문자열이 아니니 token에 저장, 연산자도 저장
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    #문자열 형의 숫자가 문장 끝까지 있는 경우
    if valProcessing:
        tokens.append(val)
    return tokens
  
        

-> 이렇게 분리된 token으로 계산을 수행한다

 

 

postfixEval

 - postfix로 나타낸 피연산자, 연산자 묶음 tokenList를 이용해 계산하는 함수 

 

def postfixEval(tokenList):
    opStack = ArrayStack()
    #피연산자 - push
    for t in tokenList:
        if type(t) is int:
            opStack.push(t)
        else: #연산자
            val1 = opStack.pop()
            val2 = opStack.pop()
            if t=='*':
                val1 *=val2
            elif t=='+':
                val1+=val2
            elif t=='/':
                val1 = val2/val1
            elif t=='-':
                val1 = val2-val1
            opStack.push(val1)
            
    val = opStack.pop()   
    return val

 

 먼저 pop()된 피 연산자가 특히 뺄셈과 나눗셈에서 뒤 자리에 오는 것에 유의하자.