[Python] 후위표기법 및 계산법

표기법의 종류

표기법은 크게 3가지로 나뉘어져 있다.

1. 전위(prefix) 표기법

   연산자를 먼저표시하고 피연산자를 나중에 표시
   ex) *+AB-CD

2. 중위(infix) 표기법

   피연산자 사이에 연산자표기 주로 우리가 사용하는 표기법이다.
   ex) (A+B) * (C-D)

3. 후위(prefix) 표기법

   피연산자를 먼저 표신한뒤 연산자를 나중에 표시
   ex) A B + C D - *

그렇다면 이런 표기법들은 왜 존재할까?

인간과 달리 컴퓨터는 내부에서 원래 스택을 활용해 중위표기법을 후위표기법으로 반환하여 연산을 한다고 한다. 이 과정에서 괄호표기가 없는 후위표기법을 이용하는것이 중위표기법 보다 속도가 빠르다고 한다.

중위표기법 -> 후위표기법 변환 방법

1. 먼저 연산자의 우선순위를 지정한다
   *,/가 +,- 보다 우선순위가 높다.
   코드를 짤 때는 아래와 같이 미리 우선순위를 설정해놓는것이 편하다.

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

2. 하위 표현식으로 만들어질 빈 리스트를 생성
3. 중위표현식을 왼쪽부터 순서대로 읽는다
4. 피연산자이면 2번에서 만들어 놓은 빈 리스트(lst)에 추가한다.
5. '('이면 stack에 추가하고, ')'이면 stack에서 '('가 나올때까지 스택을 pop()처리 해준 이후 pop()처리 한것들을 2번에서 생성해놓은 list에 추가한다.
6. 선택된게 연산자이면 stack의 위에서 선택된 연산자보다 같거나 높은 우선순위의 연산자들을 pop과 동시에 lst에 추가 해준다. 더 이상 자기보다 같거나 높은 우선순위를 가진 연산자가 없으면 stack에 추가 해준다.
7. 만약 선택된 연산자가 stack 젤 위에 있는 연산자 보다 우선순위가 높다면 다른 처리 없이 바로 stack에 추가해준다.
8. stack에 남아있는 연산자 모두 pop을 하여 lst에 추가 시켜준다.

코드로 나타내면 아래와 같다.

for t in range(1,11):
    N = int(input())
    tokens =list(map(str,input().rstrip()))     # 입력받기
    lst = []        # 빈 리스트 생성
    stack = []      # 스택 생성
    prior = {'*':3,'/':3,'+':2,'-':2,'(':1}     # 우선순위 설정
    for n in range(len(tokens)):    # 토큰의 길이만큼 반복하여
        if tokens[n].isdigit(): # 만약 숫자이면 바로 lst에 추가
            lst.append(tokens[n])
        elif tokens[n] == '(':  # (이면 바로 stack에 추가
                stack.append(tokens[n])
        elif tokens[n] == ')':  # )가 나오면 stack에서 (가 나올때까지 pop처리 및 lst에 추가. 
            while stack[-1] != '(':
                lst.append(stack.pop())
            stack.pop() # (가 나타나면 pop처리
        else:   # 그외에 경우 tokens[n]이 stack[-1]의 우선순위와 같거나 보다 작으면 tokens[n]의 우선순위가 더 커질때까지 pop
            while stack and prior[tokens[n]] <= prior[stack[-1]]:
                lst.append(stack.pop()) # pop한것들은 lst에 추가 시켜줌   
            stack.append(tokens[n]) # 위의 조건이 완료 되면 stack에 추가

    while len(stack) != 0:  # stack에 남아있는 연산자들 lst에 추가
        lst.append(stack.pop())

후위 표기법 계산법

1. 후위표현식을 왼쪽부터 한글자씩 읽는다.
2. 피연산자이면 stack에 추가를 해준다
3. 연산자이면 stack[-1]과 stack[-2]를 pop해준뒤 해당 연산자로 계산을 해준다.

• 아래의 코드들은 저 스스로 짠것이기 때문에 더 좋은 방법이 있을수 있으니 참고만 해주시면 좋겠습니다.

 o   op_check = ['+','/','*','-']    # 연산자 체크를 위해 미리 생성
    stack =[]   # 피연산자 바로 추가할 리스트 생성
    a1=0   # stack[-1]을 위한 변수 생성
    a2=0  # stack[-2]을 위한 변수 생성
    for l in range(len(lst)):   # 후위표기법으로 저장되 있는 리스트의 수만큼 반복   
        if lst[l].isdigit():    # 만약 피연산자이면 바로 stack에 추가
            stack.append(int(lst[l]))
        elif lst[l] == '+': # + 이면 stack에서 2개 피연산자를 pop하여 게산해준뒤 다시 stack에 추가
            a1 = stack.pop()
            a2 = stack.pop()
            stack.append(a1 + a2)
        elif lst[l] == '-': # - 이면 stack에서 2개 피연산자를 pop하여 게산해준뒤 다시 stack에 추가
            a1 = stack.pop()
            a2 = stack.pop()
            stack.append(a1 - a2) 
        elif lst[l] == '*': # * 이면 stack에서 2개 피연산자를 pop하여 게산해준뒤 다시 stack에 추가
            a1 = stack.pop()
            a2 = stack.pop()
            stack.append(a1 * a2)
        elif lst[l] == '/': # / 이면 stack에서 2개 피연산자를 pop하여 게산해준뒤 다시 stack에 추가
            a1 = stack.pop()
            a2 = stack.pop()
            stack.append(a1 / a2)