递归验证字符串是否是有效的前缀表达式?
我对社区相当陌生,但我在这里看到了一些有用的帖子,所以我想我会问一下。
我有一个作业问题,要求我们递归地检查给定字符串是否是由以下两个规则(标准)给出的有效前缀表达式:
- 变量 (az) 是前缀表达式
- 如果 O 是二元运算符,并且 F 和 E 是前缀表达式,OFE
现在,我得到了评估并查看了前缀到中缀算法,但我一生都无法弄清楚如何实现评估方法(因为我只需要检查如果它是有效的,那么不是例如+ab)。
我知道这些问题的大部分实现都是使用堆栈完成的,但我不知道如何在这里递归地完成它......一些帮助将非常感激。
I'm rather new to the community but I've seen some helpful posts on here so I thought I'd ask.
I've got a homework question that asks us to recursively check whether a given string is a valid prefix expression given by the two following rules (standard):
- Variables (a-z) are prefix expressions
- If O is a binary operator and F and E are prefix expressions, OFE
Now, I kind of get the evaluation and have looked at the prefix-to-infix algorithms, but I can't for the life of me figure out how to implement just the evaluation methods (as I only need to check if it's valid, so not +a-b for example).
I know most of the implementation for these problems is done using stacks but I don't see how I would do it recursively here... some help would be tremendously appreciated.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

发布评论
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
这样想吧。 (我不会编写代码,因为这是您需要学习的)。
您想要检查某个字符串是否是前缀表达式,因此您有一个函数:
现在,该字符串有两种方式可以作为前缀:
所以首先,检查字符串的长度是否为 1 并且在 az 之间,如果是,则答案是肯定的。
接下来,您可以检查字符串是否以 O 开头。如果是,则需要测试字符串的其余部分以查看它是否由两个前缀表达式 (FE) 组成。
因此,您开始从 1 迭代到 length,并将每个子字符串(0->i,i->length)传递给 isPrefix()。如果两个子字符串也是有效的前缀表达式,则答案是肯定的。
否则,答案是否定的。
差不多就是这样,但具体实施取决于您。
Think of it this way. (I'm not going to write the code, since that's what you need to learn).
You want to check if a certain string is a prefix expression, so you have a function:
Now, there's two way that string could be a prefix:
So first, you check if the string has a length of one and is between a-z, and if so, the answer is yes.
Next you can check if the string starts with an O. If it does, you need to test the rest of the string to see if it is composed of two prefix expressions (FE).
So you start iterating from 1 to length, and passing each substring (0->i, i->length) into isPrefix(). If both substrings are also valid prefix expressions, the answer is yes.
Otherwise, the answer is no.
That's pretty much it, but the implementation, however, is up to you.