简易计算器优先计算级别怎么算？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

简易计算器优先计算级别怎么算？

简易计算器优先计算级别怎么算？# Programming - 葵花宝典

s*m2014-01-22 08:01

1 楼

是用OPT利用一下现在OPT长的优势
还是就直接申请H1B呢？
各有什么优劣？
请过来人指教一下
谢谢啦！

p*y2014-01-22 08:01

2 楼

【以下文字转载自 ClassicalMusic 讨论区】
发信人: purity (purity), 信区: ClassicalMusic
标题: 请教：这是什么音乐？
发信站: BBS 未名空间站 (Fri Aug 13 21:33:01 2010, 美东)
你们知不知道从0.45min开始的音乐名称是什么？
太美了，听了很陶醉。。。。。想找出来专门听。
http://www.youtube.com/watch?v=KFR7eWn795s
0.19min那个音乐也很好听。

W*o2014-01-22 08:01

3 楼

新手在做一个简单计算器，用户可以输入类似 2 + 3 * 4 / 5 + 7 这种，怎么判断优
先级？
以前看到过带括号的算法，比如((1 + 2) * 3 + 2) / 2，知道能用两个Stack解决。
但是我的计算器界面没有括号输ru
谢谢赐教！

i*t2014-01-22 08:01

4 楼

opt+h1b

p*e2014-01-22 08:01

5 楼

这是神秘园第一张专辑里面的同名曲目
Song from a Secret Garden
http://www.youtube.com/watch?v=wasYNNfnfVE

【在 p****y 的大作中提到】

: 【以下文字转载自 ClassicalMusic 讨论区】
: 发信人: purity (purity), 信区: ClassicalMusic
: 标题: 请教：这是什么音乐？
: 发信站: BBS 未名空间站 (Fri Aug 13 21:33:01 2010, 美东)
: 你们知不知道从0.45min开始的音乐名称是什么？
: 太美了，听了很陶醉。。。。。想找出来专门听。
: http://www.youtube.com/watch?v=KFR7eWn795s
: 0.19min那个音乐也很好听。

z*e2014-01-22 08:01

6 楼

use ruby

p*y2014-01-22 08:01

7 楼

太好了，谢谢！
你还知不知道0.18min那个音乐的名称？也很好听！

【在 p**e 的大作中提到】

: 这是神秘园第一张专辑里面的同名曲目
: Song from a Secret Garden
: http://www.youtube.com/watch?v=wasYNNfnfVE

W*o2014-01-22 08:01

8 楼

我想请教一下思路，语言不能用Ruby，谢谢老赵

【在 z****e 的大作中提到】

: use ruby

p*e2014-01-22 08:01

9 楼

也是神秘园的
后期专辑里的一个，名字叫The Promise
http://www.youtube.com/watch?v=sqxbZq7d86Q

【在 p****y 的大作中提到】

: 太好了，谢谢！
: 你还知不知道0.18min那个音乐的名称？也很好听！

z*e2014-01-22 08:01

10 楼

recursive

【在 W***o 的大作中提到】

: 我想请教一下思路，语言不能用Ruby，谢谢老赵

p*y2014-01-22 08:01

11 楼

wow，你好强！太厉害了，什么歌都知道！
谢谢！

【在 p**e 的大作中提到】

: 也是神秘园的
: 后期专辑里的一个，名字叫The Promise
: http://www.youtube.com/watch?v=sqxbZq7d86Q

c*o2014-01-22 08:01

12 楼

yes, recursive, or you may say "use stack"
stack is the standard way to do this.

p*e2014-01-22 08:01

13 楼

嘿嘿，我们的id看起来像亲戚~
以前流行过一阵神秘园嘛，各种节目到处都用作背景音乐
早起的专辑听的多，熟悉一些，后来的也不怎么听了，碰巧而已

【在 p****y 的大作中提到】

: wow，你好强！太厉害了，什么歌都知道！
: 谢谢！

x*u2014-01-22 08:01

14 楼

stack

【在 W***o 的大作中提到】

: 新手在做一个简单计算器，用户可以输入类似 2 + 3 * 4 / 5 + 7 这种，怎么判断优
: 先级？
: 以前看到过带括号的算法，比如((1 + 2) * 3 + 2) / 2，知道能用两个Stack解决。
: 但是我的计算器界面没有括号输ru
: 谢谢赐教！

p*y2014-01-22 08:01

15 楼

都是纯纯家族：）
我这个ID用了好多年了，灌水灌到元始天尊，blush//

【在 p**e 的大作中提到】

: 嘿嘿，我们的id看起来像亲戚~
: 以前流行过一阵神秘园嘛，各种节目到处都用作背景音乐
: 早起的专辑听的多，熟悉一些，后来的也不怎么听了，碰巧而已

d*n2014-01-22 08:01

16 楼

有几个做法, 比如:
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 的大作中提到】

W*o2014-01-22 08:01

17 楼

wow, Thank you guys very much

【在 d****n 的大作中提到】

: 有几个做法, 比如:
: 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

p*o2014-01-22 08:01

18 楼

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 的大作中提到】

p*o2014-01-22 08:01

19 楼

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*e2014-01-22 08:01

20 楼

这个面试还是作业？
两个stack.
一个opeator,一个operand.
scan left to right.
high order op than current top of op stack. 压站
otherwise, compute
O(1)

【在 W***o 的大作中提到】

b*92014-01-22 08:01

21 楼

基本算法database已经说了，用算符优先级算法，相当于把中缀转后会缀表达式。如果
计算器的操作符很多需要扫一下计算器的语法生成一个有向图计算所有操作符栈内和栈
外的优先级，不多的话手算下就可以。具体请参考龙书前几章。

W*o2014-01-22 08:01

22 楼

不是作业也不是面试，自己最近在学vc#,所以想用图形界面做一个计算器，谢谢

【在 d******e 的大作中提到】

: 这个面试还是作业？
: 两个stack.
: 一个opeator,一个operand.
: scan left to right.
: high order op than current top of op stack. 压站
: otherwise, compute
: O(1)

W*o2014-01-22 08:01

23 楼

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*e2014-01-22 08:01

24 楼

有时间学学javascript比你做这些没用的强多了。
webkit ＋ html5 + js将来秒杀一切。

【在 W***o 的大作中提到】

: 不是作业也不是面试，自己最近在学vc#,所以想用图形界面做一个计算器，谢谢

W*o2014-01-22 08:01

25 楼

谢谢您的指点
现在就是想学一些热门的容易找到入门工作的知识 ;)

【在 d******e 的大作中提到】

: 有时间学学javascript比你做这些没用的强多了。
: webkit ＋ html5 + js将来秒杀一切。

e*o2014-01-22 08:01

26 楼

找本 compiler theory 翻翻吧。

m*72014-01-22 08:01

27 楼

我咋没看明白楼主要干啥呢？
是要
1. 写一个计算器软件，不给用户输入括号的地方，但是还要求支持用户使用括号改变
运算顺序？
2. 写一个计算器软件，能够分析不带括号的表达式？

n*t2014-01-22 08:01

28 楼

Google yacc/lex，很好玩

【在 W***o 的大作中提到】

: 不是作业也不是面试，自己最近在学vc#,所以想用图形界面做一个计算器，谢谢

t*t2014-01-22 08:01

29 楼

在不带括号的情况下, 表达式的分析就是分析某个算子是和前面的操作符结合还是后面
的操作符结合. 用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 的大作中提到】