正規表現を使用してシャントアルゴリズムを実装できますか？

Question

正規表現の点でshunting yard algorithmを実装できますか？

Answer 1

私は、これはここで回答されていると信じて：Can the shunting yard algorithm parse POSIX regular expressions?

私はあなたの質問への答えは「いいえ、あなたは は、正規表現を使用してシャントヤードアルゴリズムを実装することはできません」と言うだろう これは、 正規表現を使用して任意のHTMLを解析できないのと同じ理由によるものです。次のようなものがあります。

正規表現にはスタックがありません。シャントヤード アルゴリズムはスタックに依存しているため（ をインフィックスからRPNに変換するときにオペランドをプッシュしてポップする）、正規表現にはこのタスクを実行するための計算力 " "がありません。

これは多くの詳細を説明していますが、「正規表現」は正規の言語を定義するための一方通行です（ ）。 は、正規表現を「使用する」と言ってコンピュータに「文字の本文を見て、 の文字列が自分の言語になっているかどうかを教えてください。表現 "。通常の言語の詳細については、this most excellent answer which you and everyone reading this should upvote を指摘します。

これで、より強力な言語を作成するために、「通常の の言語」を補うための数学的な概念が必要になりました。もしあなたが に計算力のモデル の実現としてシャントヤードアルゴリズムを特徴付けるならば、アルゴリズムは がcontext-free grammarと記述されていると言われるかもしれません（ちょっとあなたが知っていることは、 リンクは表現構文解析木を使用しています例として）。push-down automata。スタックのあるもの。

オートマトンの理論と複雑さに慣れていない人は クラスですが、これらのウィキペディアの記事はあまり参考にならないかもしれません。

重要なのは、正規表現を使用してシャントを書くのに役立つかもしれない ヤードです。しかし、正規表現は、 の任意の深さを持つ操作を行うのはあまり良くありません。だから私はあまりにも多くの時間をこの問題のための正規表現の道を行くのを費やすことはありません。

Answer 2

私はそうは思わない。正規表現は通常の言語（Regular languageを参照）としか一致しませんが、中置式は文脈自由言語の一種です（Context-free languageを参照）。たとえば、適切に一致したカッコで構成される式を正規表現に一致させることはできません。