本算法具体实现了数学表达式的中缀转后缀（逆波兰），并且对表达式进行了估值，支持基本的四则运算和若干数学函数。最大的缺点是不支持负数并且不能检查表达式的合法性，考虑到其算法的复杂性，笔者决定学习正则表达式来解决这一问题。
具体算法参考以及相关代码
import sys
import math
import cmath
import operator
# define operator
operator_ad = &+&
operator_mi = &-&
operator_mu = &*&
operator_di = &/&
operator_eq = &=&
operator_lp = &(&
operator_rp = &)&
# define operator implementation
operator_implement = {
&+&: operator.add,
&-&: operator.sub,
&*&: operator.mul,
&/&: operator.div,
# define function implementation
function_implement = {
&ceil&: math.ceil, &floor&: math.floor,
&fabs&: math.fabs,
&factorial&: math.factorial,
&pow&: math.pow,
&sin&: math.sin, &cos&: math.cos, &tan&: math.tan, &asin&: math.asin, &acos&: math.acos, &atan&: math.atan,
&rad2deg&: math.degrees, &deg2rad&: math.radians,
&sinh&: math.sinh, &cosh&: math.cosh, &tanh&: math.tanh, &asinh&: math.asinh, &acosh&: math.acosh, &atanh&: math.atanh,
&erf&: math.erf, &erfc&: math.erfc, &gamma&: math.gamma, &lgamma&: math.lgamma,
&log&: math.log,
&exp&: math.exp,
&pi&: math.pi,
# define operator associativity
operator_association = {
operator_ad: &left&,
operator_mi: &left&,
operator_mu: &left&,
operator_di: &left&,
operator_eq: &left&,
# define precedence of each operator
operator_precedence = {
operator_ad: 3,
operator_mi: 3,
operator_mu: 4,
operator_di: 4,
operator_lp: -1,
operator_rp: -1,
# define argument number of each function
function_argument = {
&ceil&: 1, &floor&: 1,
&fabs&: 1,
&factorial&: 1,
&sin&: 1, &cos&: 1, &tan&: 1, &asin&: 1, &acos&: 1, &atan&: 1,
&rad2deg&: 1, &deg2rad&: 1,
&sinh&: 1, &cosh&: 1, &tanh&: 1, &asinh&: 1, &acosh&: 1, &atanh&: 1,
&erf&: 1, &erfc&: 1, &gamma&: 1, &lgamma&: 1,
# define several useful function
def precedence(op):
return operator_precedence[op]
def associativity(op):
return operator_association[op]
def is_op(c):
return operator_precedence.has_key(c) and not (is_left_paran(c) or is_right_paran(c))
def is_fun(c):
return function_argument.has_key(c)
def is_left_paran(c):
return c == operator_lp
def is_right_paran(c):
return c == operator_rp
def append_token(token, l):
if token != &&:
l.append(token)
def tokenize(expr):
tokens = []
last_token = &&
in_token = False
for c in expr:
if c == & &:
in_token = False
last_token = append_token(last_token, tokens)
elif is_op(c) or is_left_paran(c) or is_right_paran(c) or c == &,&:
in_token = False
last_token = append_token(last_token, tokens)
tokens.append(c)
in_token = True
last_token += c
if not in_token and last_token != &&:
last_token = append_token(last_token, tokens)
if in_token:
append_token(last_token, tokens)
return tokens
# shuntingyard algorithm http://en.wikipedia.org/wiki/Shunting-yard_algorithm
def infix_to_postfix(expr):
&&&converts the infix expression to postfix using the shunting yard algorithm&&&
results = []
# read a token step by step
for token in tokenize(expr):
# if the token is an operator o1, then while there is an operator token o2,
# at the top of the stack, and either o1 is left-associative and its precedence
# is equal to that of o2 or o1 has precedence less than that of o2, pop o2 off
# the stack onto the output queue.
# push o1 onto the stack.
if is_op(token):
while len(ops) & 0 and is_op(ops[-1]) and \
( (associativity(token) == &left& and precedence(token) &= precedence(ops[-1])) \
(associativity(token) == &right& and precedence(token) & precedence(ops[-1])) ):
results.append(ops.pop())
ops.append(token)
elif is_fun(token) and function_argument[token] != 0:
ops.append(token)
elif token == &,&:
while len(ops) & 0 and not is_left_paran(ops[-1]):
results.append(ops.pop())
if len(ops) == 0:
print &error: mismatched parentheses&
# if the token is a left parenthesis, then push it onto the stack.
elif is_left_paran(token):
ops.append(token)
# if the token is a right parenthesis:
# until the token at the top of the stack is a left parenthesis, pop operators
# off the stack onto the output queue.
# pop the left parenthesis from the stack, but not onto the output queue.
# if the token at the top of the stack is a function token, pop it onto the output queue
# if the stack runs out without finding a left parenthesis, then there are mismatched parentheses
elif is_right_paran(token):
while len(ops) & 0 and not is_left_paran(ops[-1]):
results.append(ops.pop())
if len(ops) == 0:
print &error: mismatched parentheses&
if is_left_paran(ops[-1]):
if is_fun(ops[-1]):
results.append(ops.pop())
# if the token is a number, then add it to the output queue
results.append(token)
# while there are no more tokens to read
# while there are still operator tokens in the stack
# if the operator on the top of the stack is a parenthesis, then there are mismatched parenthesis
# pop the operator onto the output queue
while len(ops) & 0:
if is_right_paran(ops[-1]) or is_left_paran(ops[-1]):
print &error: mismatched parentheses&
results.append(ops.pop())
return results
# test shuntingyard algorithm
# test_string = &a+b*atan(c/d)&
# print tokenize(test_string)
# print infix_to_postfix(test_string)
# evaluate reverse polish notation
def eval_rpn(expr):
for token in infix_to_postfix(expr):
if is_op(token):
y, x = opn.pop(), opn.pop()
z = operator_implement[token](x, y)
elif is_fun(token):
if function_argument[token] == 1:
x = opn.pop()
z = function_implement[token](x)
elif function_argument[token] == 0:
z = function_implement[token]
y, x = opn.pop(), opn.pop()
z = function_implement[token](x, y)
z = float(token)
opn.append(z)
return opn.pop()
test_string1 = &atan(deg2rad(180))+5*(6+pow(3.2,4.3))/(8.2+9.34)&
test_string2 = &atan(deg2rad(a)) + b*(c+pow(d, e))/(f+g)&
print test_string1
print infix_to_postfix(test_string1)
print eval_rpn(test_string1)
print infix_to_postfix(&3+(-4)*5&)
print infix_to_postfix(test_string2)
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：197次
排名：千里之外本人承诺所呈交的数学实验与数学建模作业都是本人通过学习自行进行编程独立完成,所..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数学实验与数学建模实验报告
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口