Amazon真有说的那么不好么

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 117|回复: 17
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
preortor 发表于 3 天前 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (35)
 
 
14% (6)  踩

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

您需要 登录 才可以下载或查看,没有帐号?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 自己就不知道该怎么处理了。思考了很久,也从网络上找了一下,没有找到合适的解法,于是来地理请教一下大家。
               

上一篇:刷题跳槽打卡
下一篇:安利acwing暑期刷题群
我的人缘1
肥宅快乐水 发表于 前天 11:00 | 显示全部楼层
本楼: 【顶】   50% (1)
 
 
50% (1)   【踩】
全局: 顶  68% (114)
 
 
31% (53)  踩
你有哪块不太明白, 打出来就行。

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

使用道具 举报

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

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

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

评分

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

查看全部评分

回复

使用道具 举报

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

java的int除法是 ...

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

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

评分

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

查看全部评分

回复

使用道具 举报

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

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

评分

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

查看全部评分

回复

使用道具 举报

我的人缘1
肥宅快乐水 发表于 3 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (114)
 
 
31% (53)  踩
感觉你问的问题前后不太一致

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

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

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

评分

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

查看全部评分

回复

使用道具 举报

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

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

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

使用道具 举报

我的人缘0
magicsets 发表于 3 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (211)
 
 
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 很有用的信息!

查看全部评分

回复

使用道具 举报

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

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

使用道具 举报

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

1. 存在有歧义 ...

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

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

使用道具 举报

我的人缘0
 楼主| preortor 发表于 前天 04:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (35)
 
 
14% (6)  踩
肥宅快乐水 发表于 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 发表于 前天 04:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (35)
 
 
14% (6)  踩
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 发表于 前天 04:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (35)
 
 
14% (6)  踩
肥宅快乐水 发表于 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 发表于 前天 04:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (35)
 
 
14% (6)  踩
肥宅快乐水 发表于 2018-7-13 12:48
150
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

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

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

使用道具 举报

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

1. 存在有歧义 ...

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

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

使用道具 举报

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

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

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

评分

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

查看全部评分

回复

使用道具 举报

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

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

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

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

使用道具 举报

游客
请先登录

本版积分规则

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

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






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

custom counter

GMT+8, 2018-7-16 03:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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