W***o
发帖数: 6519 | 1 新手在做一个简单计算器，用户可以输入 类似 2 + 3 * 4 / 5 + 7 这种，怎么判断优
先级？
以前看到过带括号的算法，比如((1 + 2) * 3 + 2) / 2，知道能用两个Stack解决。
但是我的计算器界面没有括号输ru
谢谢赐教！ | z****e
发帖数: 54598 | | W***o
发帖数: 6519 | 3 我想请教一下思路，语言不能用Ruby，谢谢老赵
【在 z****e 的大作中提到】
: use ruby
| z****e
发帖数: 54598 | 4 recursive
【在 W***o 的大作中提到】
: 我想请教一下思路，语言不能用Ruby，谢谢老赵
| c******o
发帖数: 1277 | 5 yes, recursive, or you may say "use stack"
stack is the standard way to do this. | x****u
发帖数: 44466 | 6 stack
【在 W***o 的大作中提到】
: 新手在做一个简单计算器，用户可以输入 类似 2 + 3 * 4 / 5 + 7 这种，怎么判断优
: 先级？
: 以前看到过带括号的算法，比如((1 + 2) * 3 + 2) / 2，知道能用两个Stack解决。
: 但是我的计算器界面没有括号输ru
: 谢谢赐教！
| d****n
发帖数: 1241 | 7 有几个做法, 比如:
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://en.wikipedia.org/wiki/Operator-precedence_parser
后者结合recursive descent parsing是现在手写parser很常用的一种方法, 这个教程
介绍了如何用：
http://llvm.org/docs/tutorial/LangImpl2.html
【在 W***o 的大作中提到】
: 新手在做一个简单计算器，用户可以输入 类似 2 + 3 * 4 / 5 + 7 这种，怎么判断优
: 先级？
: 以前看到过带括号的算法，比如((1 + 2) * 3 + 2) / 2，知道能用两个Stack解决。
: 但是我的计算器界面没有括号输ru
: 谢谢赐教！
| W***o
发帖数: 6519 | | p**o
发帖数: 3409 | 9
You may define the precedence levels for operators. E.g.,
precedence = {
'(': 0, ')': 0,
'+': 1, '-': 1,
'*': 2, '/': 2, '//': 2, '%': 2,
'^': 3, '**': 3,
}
operators = set(precedence.iterkeys())
right_associative_ops = {'^', '**',}
def infix_to_postlist (infix):
""" Simplified Shunting-yard algorithm. E.g.,
30 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
<==> 30 + ((4 * 2) / ((1 - 5) ^ (2 ^ 3)))
<==> 30 4 2 * 1 5 - 2 3 ^ ^ / +
"""
postlist = []
opstack = []
for x in infix.split(' '): # simplified tokenization
if x not in operators: # operand
postlist.append(x)
elif x == '(':
opstack.append(x)
elif x == ')':
op = opstack.pop()
while op != '(':
postlist.append(op)
op = opstack.pop()
else: # operator
if x in right_associative_ops:
while opstack and precedence[x] < precedence[opstack[-1]]:
postlist.append(opstack.pop())
else:
while opstack and precedence[x] <= precedence[opstack[-1]]:
postlist.append(opstack.pop())
opstack.append(x)
postlist.extend(reversed(opstack))
return ' '.join(postlist)
def eval_postfix (postfix):
""" Evaluate a postfix notation expression,
using a stack to store operands only.
"""
operandstack = []
for token in postfix.split(' '):
if token in operators:
x = operandstack.pop()
y = operandstack.pop()
z = eval('%s%s%s' % (x,token,y))
operandstack.append(z)
else:
operand = eval(token)
operandstack.append(operand)
assert len(operandstack)==1
return operandstack.pop()
【在 W***o 的大作中提到】
: 新手在做一个简单计算器，用户可以输入 类似 2 + 3 * 4 / 5 + 7 这种，怎么判断优
: 先级？
: 以前看到过带括号的算法，比如((1 + 2) * 3 + 2) / 2，知道能用两个Stack解决。
: 但是我的计算器界面没有括号输ru
: 谢谢赐教！
| p**o
发帖数: 3409 | 10
Alternatively, you can build your own parse tree from ground up. E.g. (
assuming fully parenthesized),
class BinTree (object):
def __init__ (self, root=None, left=None, right=None):
self.root = root
self.left = left
self.right = right
def insert_left (self, obj=None):
self.left = BinTree(obj, left=self.left)
return self.left
def insert_right (self, obj=None):
self.right = BinTree(obj, right=self.right)
return self.right
def tokenized (expression):
""" Tokenize an expression (tentatively using ' ').
"""
assert isinstance(expression, str)
return expression.split()
def build_parse_tree (expression):
""" Build parse tree.
Example input '( ( 7 + 3 ) * ( 5 - 2 ) )'.
`ptree` references (the current node of the) parse tree.
`pstack` tracks parents -- note that we assume
there are one more operands than operators,
so we essentially push the root twice to avoid
popping from an empty stack at the last ')'.
"""
ptree = BinTree()
pstack = [ptree]
for token in tokenized(expression):
if token == '(':
pstack.append(ptree)
ptree = ptree.insert_left()
elif token == ')':
ptree = pstack.pop()
elif token in ('+', '-', '*', '/'): # operators
ptree.root = token
pstack.append(ptree)
ptree = ptree.insert_right()
else: # operands
ptree.root = token
ptree = pstack.pop()
return ptree
def eval_parse_tree (ptree):
""" Evaluate a parse tree via postorder traversal.
"""
assert isinstance(ptree, BinTree)
if ptree.left and ptree.right:
leftval = eval_parse_tree(ptree.left)
rightval = eval_parse_tree(ptree.right)
# Or just `return eval('%f%s%f' % (leftval, ptree.root, rightval))`
import operator as op
fop = {'+': op.add, '-': op.sub, '*': op.mul, '/': op.div,}
return fop[ptree.root](leftval, rightval)
else:
return float(ptree.root)
def get_expression (ptree):
""" Get/Print the parse tree into an expresion
via inorder traversal.
"""
assert isinstance(ptree, BinTree)
if ptree:
if ptree.left and ptree.right:
return '(%s%s%s)' % (
get_expression(ptree.left),
ptree.root,
get_expression(ptree.right)
)
else:
return ptree.root
if __name__ == '__main__':
pt = build_parse_tree('( ( 7 + 3 ) * ( 5 - 2 ) )')
print get_expression(pt)
print eval_parse_tree(pt)
【在 p**o 的大作中提到】
:
: You may define the precedence levels for operators. E.g.,
: precedence = {
: '(': 0, ')': 0,
: '+': 1, '-': 1,
: '*': 2, '/': 2, '//': 2, '%': 2,
: '^': 3, '**': 3,
: }
: operators = set(precedence.iterkeys())
: right_associative_ops = {'^', '**',}
| | | d******e
发帖数: 2265 | 11 这个面试还是作业？
两个stack.
一个opeator,一个operand.
scan left to right.
high order op than current top of op stack. 压站
otherwise, compute
O(1)
【在 W***o 的大作中提到】
: 新手在做一个简单计算器，用户可以输入 类似 2 + 3 * 4 / 5 + 7 这种，怎么判断优
: 先级？
: 以前看到过带括号的算法，比如((1 + 2) * 3 + 2) / 2，知道能用两个Stack解决。
: 但是我的计算器界面没有括号输ru
: 谢谢赐教！
| b*****9
发帖数: 89 | 12 基本算法database已经说了，用算符优先级算法，相当于把中缀转后会缀表达式。如果
计算器的操作符很多需要扫一下计算器的语法生成一个有向图计算所有操作符栈内和栈
外的优先级，不多的话手算下就可以。具体请参考龙书前几章。 | W***o
发帖数: 6519 | 13 不是作业也不是面试，自己最近在学vc#,所以想用图形界面做一个计算器，谢谢
【在 d******e 的大作中提到】
: 这个面试还是作业？
: 两个stack.
: 一个opeator,一个operand.
: scan left to right.
: high order op than current top of op stack. 压站
: otherwise, compute
: O(1)
| W***o
发帖数: 6519 | 14 very helpful, thanks a lot!
【在 p**o 的大作中提到】
:
: Alternatively, you can build your own parse tree from ground up. E.g. (
: assuming fully parenthesized),
: class BinTree (object):
: def __init__ (self, root=None, left=None, right=None):
: self.root = root
: self.left = left
: self.right = right
: def insert_left (self, obj=None):
: self.left = BinTree(obj, left=self.left)
| d******e
发帖数: 2265 | 15 有时间学学javascript比你做这些没用的强多了。
webkit ＋ html5 + js将来秒杀一切。
【在 W***o 的大作中提到】
: 不是作业也不是面试，自己最近在学vc#,所以想用图形界面做一个计算器，谢谢
| W***o
发帖数: 6519 | 16 谢谢您的指点
现在就是想学一些热门的容易找到入门工作的知识 ;)
【在 d******e 的大作中提到】
: 有时间学学javascript比你做这些没用的强多了。
: webkit ＋ html5 + js将来秒杀一切。
| e*******o
发帖数: 4654 | 17 找本 compiler theory 翻翻吧。 | m****7
发帖数: 69 | 18 我咋没看明白楼主要干啥呢？
是要
1. 写一个计算器软件，不给用户输入括号的地方，但是还要求支持用户使用括号改变
运算顺序？
2. 写一个计算器软件，能够分析不带括号的表达式？ | n*****t
发帖数: 22014 | 19 Google yacc/lex，很好玩
【在 W***o 的大作中提到】
: 不是作业也不是面试，自己最近在学vc#,所以想用图形界面做一个计算器，谢谢
| t****t
发帖数: 6806 | 20 在不带括号的情况下, 表达式的分析就是分析某个算子是和前面的操作符结合还是后面
的操作符结合. 用C语言的术语来说, 优先级高的先结合, 优先级一样的, 看结合性.
比如:
1+2*3 ==> 1+(2*3)
1*2+3 ==> (1*2)+3
1-2-3 ==> (1-2)-3 [-是左结合的操作]
a=b=c ==> a=(b=c) [=是右结合的操作]
【在 W***o 的大作中提到】
: 新手在做一个简单计算器，用户可以输入 类似 2 + 3 * 4 / 5 + 7 这种，怎么判断优
: 先级？
: 以前看到过带括号的算法，比如((1 + 2) * 3 + 2) / 2，知道能用两个Stack解决。
: 但是我的计算器界面没有括号输ru
: 谢谢赐教！
|
|
