algorithm - 入力文字列が正しい RPN 式であるかどうかを確認する最速の方法は何ですか?

Question

メソッド/関数に引数として渡された文字列が逆ポーランド記法の意味で正しいステートメントであるかどうかを確認するタスクに出くわしました。小文字のアルファベット、操作記号、および整数を含めることができます。すべての文字を個別に読み取り、実際に式全体を評価しようとするよりも速くチェックする方法はありますか?

Answer 1

式全体を評価する必要はありませんが、トークンに分割する必要があり、すべての演算子の価数 (つまり、オペランドの数) を知る必要があります。簡単にするために、オペランドの価数を 0 とします。次に、次の操作を行います。

Set stack_size to 0;
For Each token In expression:
    Set stack_size to stack_size + 1 - valence(token)
    If stack_size <= 0: Report failure
If stack_size == 1: Report success
Else              : Report failure

_単項マイナスの使用例。

expression:     3 4 + 1 * _
stack_size:   0 1 2 1 2 1 1 -> success

expression:     2 3 4 + 1 * _
stack_size:   0 1 2 3 2 3 2 2 -> failure (not 1 at the end)

expression:     2 3 + + 1 * _
stack_size:   0 1 2 1 0       -> failure (stack_size <= 0)

Answer 2

解析テーブルを使用して、逆ポーランド記法を認識することができます。各文字を確認する必要がありますが、高速です。