후위 표기법을 사용할 일이 있어서 찾다 보니 아래 사이트를 참고하게 됨.
주로 참고한 사이트
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 )"))
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
댓글 없음:
댓글 쓰기