递归验证字符串是否是有效的前缀表达式？

我对社区颇为陌生，但我在这里看到了一些有用的帖子，所以我想我会问。递归验证字符串是否是有效的前缀表达式？

我有一门功课疑问，要求我们递归查询给定的字符串是否是由以下两个规则（标准）给出一个有效的前缀表达式：

变量（亚利桑那州）的前缀表达式
如果o是一个二元运算符和F和E是前缀表达式，OFE

现在，我种得到的评价，并看了看前缀至缀算法，但我不能为我的生活想出了如何实施评估方法ds（因为我只需要检查它是否有效，所以不是+ a-b）。

我知道这些问题的大部分实现是使用堆栈完成的，但我没有看到我将如何递归地在这里执行......有些帮助将得到极大的赞赏。

来源

2011-10-12 user991710

想想这样。（我不会写代码，因为这是你需要学习的）。

你要检查是否某些字符串是前缀表达式，让您拥有一个功能：

boolean isPrefix(string)

现在，有两路该字符串可能是一个前缀：

这是一个从AZ字符
它在格式O（前缀）（前缀）

因此，首先，你CH eck如果字符串的长度为1且在a-z之间，如果是，则答案为是。

接下来，您可以检查字符串是否以O开头。如果是，则需要测试字符串的其余部分以查看它是否由两个前缀表达式（FE）组成。

所以你开始迭代从1到长度，并将每个子串（0-> i，i-> length）传递给isPrefix（）。如果两个子字符串都是有效的前缀表达式，那么答案是肯定的。

否则，答案是否定的。

这几乎是它，但是，实施取决于你。

来源

2011-10-12 15:25:08

谢谢你的子，这是令人难以置信的写得很好，我打自己没有思考它像早先（虽然这是一种强力方法，我们的教授对效率非常挑剔......尽管我会漠视这个特殊问题）。然而，尽管我已经实现了一些在纸上签出的东西，但似乎有一个我无法发现的轻微缺陷。这里是代码片段：http://pastebin.com/Lk5mHM7R 我明白如果你有更好的事情要做，我会在此期间继续调试。 – user991710

@ uer991710将大括号括在第一个if，else else {}语句绑定到if（in.equals（vars [i]））而不是if（in.length（）== 1）。我强烈建议在您的IDE中启用代码格式，因为它可以更容易地检测到。 –

我不敢相信我错过了。我试图保存几行，并且必须忘记，其他内容仅适用于最近的'if'。我最近一直在阅读一些Python，所以我必须有一个关于缩进的大脑放屁。然而，关于格式化的要点。谢谢。 – user991710

我不知道我完全理解这一点，但我想你应该有一个像checkPrefixIn(String s)一些方法，看起来仅在给定的String的一部分，返回true如果它仅仅是一个前缀，false如果是只有运营商（或无效字符），或checkPrefixIn(partOfS)，返回值，其中partOfS是输入s

来源

2011-10-12 15:25:12 Supuhstar

这是指表达式的前缀表示法（http://www.cs.man.ac.uk/~pjj/cs212/fix.html），而不是文学前缀。 –

感谢您的输入：3 – Supuhstar

递归验证字符串是否是有效的前缀表达式？

回答

相关问题