Mock interview for data science
仅限两天:购买DS501或者DS601,全站课程15% off

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 356|回复: 17
收起左侧

[编程题] 关于postfix表达式用栈计算时的问题

[复制链接] |试试Instant~
我的人缘0
preortor 发表于 2018-7-13 11:48:21 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (36)
 
 
18% (8)  踩

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
最近学习栈的应用。非常经典的postfix表达式计算问题遇到了两次了。基本的代码应用我是可以完成的,给一个postfix式子,比如2 3 4 * +,计算结果。我的代码大概如下:

       
                                if(Character.isDigit(c)) {
                                        stack.push(Integer.parseInt(String.valueOf(c)));
                                }                       

                                if(c == '+') {
                                        a = stack.pop();
                                        b = stack.pop();
                                        stack.push(b+a);
                                }if(c == '-') {
                                        a = stack.pop();
                                        b = stack.pop();
                                        stack.push(b-a);
                                }if(c == '*') {
                                        a = stack.pop();
                                        b = stack.pop();
                                        stack.push(b*a);
                                }if(c == '/') {
                                        a = stack.pop();
                                        b = stack.pop();
                                        stack.push(b/a);
                                }
                                else {
                                       
                                }
                       
                }
        return stack.peek();

但是,如果式子里有负数,或者“/” (java int不能整除)的情况下,比如: -1 - -2 * -12 / -4 自己就不知道该怎么处理了。思考了很久,也从网络上找了一下,没有找到合适的解法,于是来地理请教一下大家。
               

上一篇:刷题跳槽打卡
下一篇:东湾san leandro刷题的小伙伴招招手呗~?
我的人缘1
肥宅快乐水 发表于 2018-7-14 11:00:34 | 显示全部楼层
本楼: 【顶】   50% (1)
 
 
50% (1)   【踩】
全局: 顶  82% (807)
 
 
17% (176)  踩
你有哪块不太明白, 打出来就行。

不过你打的时候确保知道自己在问什么,而不是闭着眼睛把自己也不知道想要什么答案的问题扔出来。尽量先把自己该做的事情都做了, 比如真的找不到答案。。
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
magicsets 发表于 2018-7-14 04:41:25 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (342)
 
 
1% (6)  踩
preortor 发表于 2018-7-14 04:28
我现在终于明白该怎么解决了。只要通过String.split(" ")函数,分隔数字和运算符号就可以了。只要不是加 ...

作为follow up你可以试着解决负号与后面的数字有空格的情况... 这才是真正比较难的部分

“假定负号与数字连在一起”是一种词法(lexer)方面的trick,并没有触及到关于负号和减号的本质的语法(grammar)二义性问题

评分

参与人数 1大米 +5 收起 理由
preortor + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
magicsets 发表于 2018-7-13 13:14:50 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (342)
 
 
1% (6)  踩
preortor 发表于 2018-7-13 12:59
谢谢呀,所以这里我需要考虑写一个syntax-directed translator来完成对负数的处理?

java的int除法是 ...

是的,然后要做到隐式类型转换你需要同时记录值以及值的类型(Type),当两个不同类型的值进行运算时,自动cast其中一个。

有空我写一份样例代码...

评分

参与人数 1大米 +5 收起 理由
preortor + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘1
肥宅快乐水 发表于 2018-7-13 12:48:32 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  82% (807)
 
 
17% (176)  踩
preortor 发表于 2018-7-13 12:37
谢谢提醒,我自己都没有注意到这个只能计算个位数。如果要计算多位数和负数,应该怎么处理呢?

150
https://leetcode.com/problems/ev ... tation/description/

评分

参与人数 1大米 +5 收起 理由
preortor + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘1
肥宅快乐水 发表于 2018-7-13 12:18:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (807)
 
 
17% (176)  踩
感觉你问的问题前后不太一致

如果是 postfix 应该可以直接按你的方法做。 只不过负数不好处理。

你第二个问题是正经式子直接value, basic calculator 1234 应该可以满足你第二个问题, 只不过也不包含负数。

然后你stack push integer这段, 每个都只能是个位数的加减吗

评分

参与人数 1大米 +5 收起 理由
preortor + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| preortor 发表于 2018-7-13 12:37:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (36)
 
 
18% (8)  踩
肥宅快乐水 发表于 2018-7-13 12:18
感觉你问的问题前后不太一致

如果是 postfix 应该可以直接按你的方法做。 只不过负数不好处理。

谢谢提醒,我自己都没有注意到这个只能计算个位数。如果要计算多位数和负数,应该怎么处理呢?
回复

使用道具 举报

我的人缘0
magicsets 发表于 2018-7-13 12:46:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (342)
 
 
1% (6)  踩
Postfix表达式中如果重载运算符"-"既表示二元减号又表示一元负号的话,那么有两个问题:

1. 存在有歧义的表达式
例如:1 1 - -
即可解释为 1 - (-1),又可解释为 - (1 - 1)

对于歧义的问题,类似于infix表达式我们可以通过规定operator的优先级来解决。例如规定一元负号优先级较高,那么上述表达式第一个"-"号优先解释为负号。

2. 不存在高效的文法解析
这是最致命的问题,简单来说就是你得写递归/回溯代码。

考虑一个例子:
1 1 - 1 + 1 + 1 + ... (这里重复任意多次 "1 +")1 + +

在看到最后一个加号之前,是无法确定第一个"-"号到底代表二元减号还是一元负号的,那么该表达式:
(1) 不适用任意LL(k)文法 -- 类似于ANTLR/JavaCC这些parser generator所使用的文法。
(2) 不适用任意LALR(k)文法 -- 在第一个"-"处就会发生shift/reduce冲突。

总结一下,解决方式:
- 对于重载的"-"运算符,规定优先级,惯例是一元负号优先级较高
- 写一个递归/回溯的syntax-directed translator,当然递归你也可以手动stack,但这里stack保存的上下文就比较复杂了,不是简单的中间计算值。


然后关于整除的问题,“Java int不能整除”是想要不能整除的时候自动转换为浮点类型吗,类似于Python或者R的除法运算特性?

评分

参与人数 1大米 +5 收起 理由
preortor + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| preortor 发表于 2018-7-13 12:50:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (36)
 
 
18% (8)  踩
肥宅快乐水 发表于 2018-7-13 12:48
150
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

哇,居然是leetcode的题目。谢谢呀,我去看看。
回复

使用道具 举报

我的人缘0
 楼主| preortor 发表于 2018-7-13 12:59:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (36)
 
 
18% (8)  踩
magicsets 发表于 2018-7-13 12:46
Postfix表达式中如果重载运算符"-"既表示二元减号又表示一元负号的话,那么有两个问题:

1. 存在有歧义 ...

谢谢呀,所以这里我需要考虑写一个syntax-directed translator来完成对负数的处理?

java的int除法是不会自动转换的,12/3是4, 13/3也是4。只有先转化成double 和 float 才可以。
回复

使用道具 举报

我的人缘0
 楼主| preortor 发表于 2018-7-14 04:00:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (36)
 
 
18% (8)  踩
肥宅快乐水 发表于 2018-7-13 12:48
150
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

我做完了这道题目,有一点出入,就是这道题本身的input就是Sring[] 而不是 String;用for each loop直接转string 去int。所以规避了多位数的问题。这启发了我,我也可以直接用split函数把给定的String 转成 Sring[] 。但这道题目没有负数和括号的情况。所以我还是要再想想。但括号的思路应该是一样的,看到“(”就放进去,看到“)”就pop,先看是不是()是一致的。然后再利用stack计算。
负数的话,我在网络上看到是把-x理解成0-x。我在想,能不能每次看到负号,都转化成0-x。
回复

使用道具 举报

我的人缘0
 楼主| preortor 发表于 2018-7-14 04:02:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (36)
 
 
18% (8)  踩
magicsets 发表于 2018-7-13 12:46
Postfix表达式中如果重载运算符"-"既表示二元减号又表示一元负号的话,那么有两个问题:

1. 存在有歧义 ...

我做完了这道题目:https://leetcode.com/problems/ev ... tation/description/
leetcode 150.

这道题和我面对的学校里的练习有一点出入,就是这道题本身的input就是Sring[] 而不是 String。所以可以用for each loop直接转string 去int。所以规避了多位数的问题。这启发了我,我也可以直接用split函数把给定的String 转成 Sring[] 。这样就可以计算多位数了。


但这道题目没有负数和括号的情况。我准备把每次负号都转化成0-x。理论上应该是可以的。我准备试试。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|联系我们&一亩三分地论坛声明

GMT+8, 2018-11-19 19:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表