📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: preortor
跳转到指定楼层
上一主题 下一主题
收起左侧

关于postfix表达式用栈计算时的问题

🔗
 楼主| preortor 2018-7-14 04:21:56 | 只看该作者
全局:
肥宅快乐水 发表于 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());
        }

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

使用道具 举报

🔗
 楼主| preortor 2018-7-14 04:26:20 | 只看该作者
全局:
肥宅快乐水 发表于 2018-7-13 12:48
150
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

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

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

使用道具 举报

🔗
 楼主| preortor 2018-7-14 04:28:46 | 只看该作者
全局:
magicsets 发表于 2018-7-13 12:46
Postfix表达式中如果重载运算符"-"既表示二元减号又表示一元负号的话,那么有两个问题:

1. 存在有歧义 ...

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

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

使用道具 举报

🔗
magicsets 2018-7-14 04:35:40 | 只看该作者
全局:
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 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
magicsets 2018-7-14 04:41:25 | 只看该作者
全局:
preortor 发表于 2018-7-14 04:28
我现在终于明白该怎么解决了。只要通过String.split(" ")函数,分隔数字和运算符号就可以了。只要不是加 ...

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

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

评分

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

查看全部评分

回复

使用道具 举报

全局:
preortor 发表于 2018-7-14 04:26
哦我明白了。因为数字和加减号都是通过“ ”隔开的。所以每次用split(" "),就会自动区别负数里的负号和 ...

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

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

评分

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

查看全部评分

回复

使用道具 举报

全局:
你有哪块不太明白, 打出来就行。

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

使用道具 举报

全局:
肥宅快乐水 发表于 2018-7-14 11:00
你有哪块不太明白, 打出来就行。

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

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

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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