【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 204|回复: 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)   【踩】
全局: 顶  78% (571)
 
 
21% (152)  踩
你有哪块不太明白, 打出来就行。

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

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
magicsets 发表于 2018-7-14 04:41:25 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (254)
 
 
2% (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)   【踩】
全局: 顶  97% (254)
 
 
2% (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)   【踩】
全局: 顶  78% (571)
 
 
21% (152)  踩
preortor 发表于 2018-7-13 12:37
谢谢提醒,我自己都没有注意到这个只能计算个位数。如果要计算多位数和负数,应该怎么处理呢?

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

评分

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

查看全部评分

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

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

如果是 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)   【踩】
全局: 顶  97% (254)
 
 
2% (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 很有用的信息!

查看全部评分

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘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。

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘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。理论上应该是可以的。我准备试试。
回复

使用道具 举报

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

我现在有点迷茫,因为我利用这个代码:

*/
        public int evaluatePostfix() {
                // TODO
                String[] tokens = postfix.split(" ");
                 if(tokens.length == 0 || tokens == null) return 0;
                int a = 0,b = 0;
                Stack<Integer> res = new Stack<Integer>();
                //use for each loop to get every string from the token
                for(String c: tokens){
                    if(!isOperator(c)){
                        res.push(Integer.parseInt(c));
                    }else{
                        if(!res.isEmpty()){
                             b = res.pop();
                        }
                      
                      if(!res.isEmpty()){
                             a = res.pop();
                        }
                      
                        res.push( eval(a, b, c.charAt(0)));
                    }
                }
                if(res.isEmpty()){
                    return 0;
                }else {
                    return res.pop();
            }
            }
            
       
            private boolean isOperator(String s) {
                if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
                    return true;
                }
                else {
                    return false;
                }
        }
            
            
            private int eval(int a, int b, char op){
                if(op == '+'){
                    return a + b;
                } if(op == '-'){
                    return a - b;
                }if(op == '*'){
                    return a * b;
                }if(op == '/'){
                    return a / b;
                }else{
                     return 0;
                }
            }

成功过了有负数的test。
public void test4() {
                String input = "-1 - -2 * -12 / -4";
                InToPost output = new InToPost(input);
                assertEquals(5, output.evaluatePostfix());
        }

我现在不知道是为什么。。。
回复

使用道具 举报

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

哦我明白了。因为数字和加减号都是通过“ ”隔开的。所以每次用split(" "),就会自动区别负数里的负号和减号。
然后只要不是加减号,就会被parseInt(c)自动转化为数字。
这就是为什么我利用lc的思路,解决了更复杂的学校里的例子。

太感谢了,把lc类似的题目找给我。谢谢呀。
回复

使用道具 举报

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

1. 存在有歧义 ...

我现在终于明白该怎么解决了。只要通过String.split(" ")函数,分隔数字和运算符号就可以了。只要不是加减号,就会被parseInt(c)自动转化为数字。

这样就非常顺利的做出来了。
回复

使用道具 举报

我的人缘0
magicsets 发表于 2018-7-14 04:35:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (254)
 
 
2% (6)  踩
preortor 发表于 2018-7-14 04:26
哦我明白了。因为数字和加减号都是通过“ ”隔开的。所以每次用split(" "),就会自动区别负数里的负号和 ...

你写的代码是计算中序(infix)表示式的,并没有解决postfix的问题... 考虑下面两个postfix式子:
String input1 = "1 1 1 1 1 - - - - + + +"
String input2 = "1 1 1 1 1 - - - - + + + +"
有没有办法计算出正确结果?

其次用split(" ")是一种hack,这种方法可行的前提是输入里一元符号与后面的数字没有空格,如果加上空格:
String input = "- 1 - - 2 * - 12 / - 4";
代码就行不通了

评分

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

查看全部评分

回复

使用道具 举报

我的人缘1
肥宅快乐水 发表于 2018-7-14 05:05:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  78% (571)
 
 
21% (152)  踩
preortor 发表于 2018-7-14 04:26
哦我明白了。因为数字和加减号都是通过“ ”隔开的。所以每次用split(" "),就会自动区别负数里的负号和 ...

大凶呆你这个自言自语真的是没谁了.

你这个post fix 跟你想解答的问题似乎不是一回事.. 你开心就好..

评分

参与人数 1大米 +5 收起 理由
preortor + 5 不好意思,我再想想。小菜鸡一枚。。。

查看全部评分

回复

使用道具 举报

我的人缘1
肥宅快乐水 发表于 2018-7-14 11:01:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  78% (571)
 
 
21% (152)  踩
肥宅快乐水 发表于 2018-7-14 11:00
你有哪块不太明白, 打出来就行。

不过你打的时候确保知道自己在问什么,而不是闭着眼睛把自己也不知道 ...

因为我看你的问题有点没头没尾, 不知道到底是你理解不到位, 还是理解错了。

如果你不懂, 大大方方什么毛病都没有。我跟你解释, 也是我学习的过程。
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-23 14:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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