遞歸驗證字符串是否是有效的前綴表達式？

我對社區頗爲陌生，但我在這裏看到了一些有用的帖子，所以我想我會問。遞歸驗證字符串是否是有效的前綴表達式？

我有一門功課疑問，要求我們遞歸查詢給定的字符串是否是由以下兩個規則（標準）給出一個有效的前綴表達式：

變量（亞利桑那州）的前綴表達式
如果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

遞歸驗證字符串是否是有效的前綴表達式？

回答

相關問題