2016년 12월 17일 토요일

[Link] 후위 표기법(postfix) 및 계산

후위 표기법을 사용할 일이 있어서 찾다 보니 아래 사이트를 참고하게 됨. 

주로 참고한 사이트
http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html

설명이 영어고 예제가 python이지만
설명이 자세하고 코드가 정말 깔끔해서 참고하기 좋음.

보관을 위해 코드를 퍼오면 다음과 같음.
일단 트리를 사용해서 구현한 코드는 아님.

infix => postfix

from pythonds.basic.stack import Stack
def infixToPostfix(infixexpr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = Stack()
    postfixList = []
    tokenList = infixexpr.split()
    for token in tokenList:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            while (not opStack.isEmpty()) and \
               (prec[opStack.peek()] >= prec[token]):
                  postfixList.append(opStack.pop())
            opStack.push(token)
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return " ".join(postfixList)
print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

postfix 계산

from pythonds.basic.stack import Stack
def postfixEval(postfixExpr):
    operandStack = Stack()
    tokenList = postfixExpr.split()
    for token in tokenList:
        if token in "0123456789":
            operandStack.push(int(token))
        else:
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token,operand1,operand2)
            operandStack.push(result)
    return operandStack.pop()
def doMath(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2
print(postfixEval('7 8 + 3 2 + /'))

대충 C#으로 옮겨본 코드.. 뭐 만들다 만거라 문제는 많음.
https://github.com/hallower/dumbCalculator/blob/master/CalculatorImpl/CalculatorImpl/CalculatorImpl.cs


그리고 한글로 전반적인 내용과
C++로 구현된 예제가 괜찮은 사이트 이고
트리를 사용하여 구현한 코드임.
http://ehclub.co.kr/1258

댓글 없음:

댓글 쓰기