후위 수식(postfix) 정리

<후위 수식 평가>

1 후위 수식에서 읽은 토큰이 피연산자이면 스택에 넣는다

2. 토큰이 연산자이면 스택에서 피연산자 2개를 꺼내서 계산한 후 그 결과 값을 다시 스택에 넣는다

3. 모든 토큰이 입력되면 스택에 마지막으로 저장된 계산값을 꺼내서 반환한다.

 

- 순서 : 피연산자 피연산자 연산자

- 연산자의 우선순위가 없고 괄호를 사용하지 않는다

- 왼쪽에서 오른쪽 방향으로 1회 스캔하여 계산하므로 프로그래밍하기 쉽다

- 사람이 직관적으로이해하기 어렵다

 

class Sym:
    OPEN_B = 1
    CLOSE_B = 2
    PLUS = 3
    MINUS = 4
    TIMES = 5
    DIVIDE = 6
    MOD = 7
    OPERAND = 8


class Expression:
    def __init__(self, expr):
        self.stack = []
        self.size = 100
        self.expr = expr
        self.top = -1

    def push(self, item):
        self.top += 1
        self.stack.append(item)
        self.show_stack()

    def pop(self):
        if len(self.stack)>0:
            self.top -= 1
        else : print("Stack empty")

    def show_stack(self):
        print(self.stack)

    def eval_postfix(self):
        for sym in self.expr:
            print(sym, end = '')
            sym_type = self.getSymtype(sym)

            #토큰이 피연산자인 경우 정수형으로 변환 
            if sym_type == Sym.OPERAND:
                self.push(int(sym))

            else:
                op2 = self.pop()
                op1 = self.pop()

                if sym_type == Sym.PLUS:
                    self.push(op1+op2)
                elif sym_type == Sym.MINUS:
                    self.push(op1 - op2)
                elif sym_type == Sym.TIMES:
                    self.push(op1 * op2)
                elif sym_type == Sym.DIVIDE:
                    self.push(op1 // op2)
                elif sym_type == Sym.MOD:
                    self.push(op1 % op2)

            return self.pop()

    def getSymtype(self, sym):
        if sym == '(' : sym_type = Sym.OPEN_B
        elif sym == ')': sym_type = Sym.CLOSE_B
        elif sym == '+': sym_type = Sym.PLUS
        elif sym == '-': sym_type = Sym.MINUS
        elif sym == '*': sym_type = Sym.TIMES
        elif sym == '/': sym_type = Sym.DIVIDE
        elif sym == '%': sym_type = Sym.MOD
        else: sym_type = Sym.OPERAND
        return sym_type


for expr in ["57*9+34/-", "936+5-7*64-*"]:
    e = Expression(expr)
    print("수식 :", expr)
    print("결과값 : ", e.eval_postfix())
    print()

 

 

 

수식 : 57*9+34/-

5 [5]
7 [5, 7]
* [35]
9 [35, 9]
+ [44]
3 [44, 3]
4 [44, 3, 4]
/ [44, 0]
- [44]

결과값 = 44

수식 : 936+5-/7*64-*

9 [9]
3 [9, 3]
6 [9, 3, 6]
+ [9, 9]
5 [9, 9, 5]
- [9, 4]
/ [2]
7 [2, 7]
* [14]
6 [14, 6]
4 [14, 6, 4]
- [14, 2]
* [28]

결과값 = 28