📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1874| 回复: 17
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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 自己就不知道该怎么处理了。思考了很久,也从网络上找了一下,没有找到合适的解法,于是来地理请教一下大家。
               

上一篇:刷题跳槽打卡
下一篇:偏数学类的题会考么
全局:
你有哪块不太明白, 打出来就行。

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

使用道具 举报

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

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

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

评分

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

查看全部评分

回复

使用道具 举报

推荐
magicsets 2018-7-13 13:14:50 | 只看该作者
全局:
preortor 发表于 2018-7-13 12:59
谢谢呀,所以这里我需要考虑写一个syntax-directed translator来完成对负数的处理?

java的int除法是 ...

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

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

评分

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

查看全部评分

回复

使用道具 举报

全局:
感觉你问的问题前后不太一致

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

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

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

评分

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

查看全部评分

回复

使用道具 举报

🔗
 楼主| preortor 2018-7-13 12:37:34 | 只看该作者
全局:
肥宅快乐水 发表于 2018-7-13 12:18
感觉你问的问题前后不太一致

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

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

使用道具 举报

🔗
magicsets 2018-7-13 12:46:29 | 只看该作者
全局:
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 很有用的信息!

查看全部评分

回复

使用道具 举报

全局:
preortor 发表于 2018-7-13 12:37
谢谢提醒,我自己都没有注意到这个只能计算个位数。如果要计算多位数和负数,应该怎么处理呢?

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

评分

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

查看全部评分

回复

使用道具 举报

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

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

使用道具 举报

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

1. 存在有歧义 ...

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

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

使用道具 举报

🔗
 楼主| preortor 2018-7-14 04:00:51 | 只看该作者
全局:
肥宅快乐水 发表于 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。
回复

使用道具 举报

🔗
 楼主| preortor 2018-7-14 04:02:22 | 只看该作者
全局:
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。理论上应该是可以的。我准备试试。
回复

使用道具 举报

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

本版积分规则

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