8

Shunting-Yard アルゴリズムを使用して式を評価します。アルゴリズムを適用するだけで式を検証できます。オペランドの欠落、括弧の不一致などがあると失敗します。ただし、Shunting-Yard アルゴリズムには、人間が読めるインフィックスよりも多くの構文がサポートされています。例えば、

1 + 2
+ 1 2
1 2 +

Shunting-Yard アルゴリズムへの入力として「1+2」を提供するすべての許容可能な方法です。'+ 1 2' と '1 2 +' は有効なインフィックスではありませんが、標準の Shunting-Yard アルゴリズムで処理できます。アルゴリズムは実際には順序を気にしません。「最も近い」オペランドを取得する優先順位に従って演算子を適用します。

入力を人間が読める有効なインフィックスに制限したいと思います。Shunting-Yard アルゴリズムを変更して無効な infix で失敗するようにするか、Shunting-Yard を使用する前に infix 検証を提供する方法を探しています。

これを行うための公開された手法を知っている人はいますか? 基本演算子、カスタム演算子、括弧、および関数 (複数の引数を持つ) の両方をサポートする必要があります。基本的なオペレーター以外で動作するものはオンラインで見たことがありません。

ありがとう

4

2 に答える 2

10

私の問題の解決策は、ウィキペディアに投稿されたアルゴリズムを、Rici が推奨するステート マシンで強化することでした。他の人に役立つ可能性があるため、ここに疑似コードを投稿します。

Support two states, ExpectOperand and ExpectOperator.

Set State to ExpectOperand
While there are tokens to read:
    If token is a constant (number)
        Error if state is not ExpectOperand.
        Push token to output queue.
        Set state to ExpectOperator.
    If token is a variable.
        Error if state is not ExpectOperand.
        Push token to output queue.
        Set state to ExpectOperator.
    If token is an argument separator (a comma).
        Error if state is not ExpectOperator.
        Until the top of the operator stack is a left parenthesis  (don't pop the left parenthesis).
            Push the top token of the stack to the output queue.
            If no left parenthesis is encountered then error.  Either the separator was misplaced or the parentheses were mismatched.
        Set state to ExpectOperand.
    If token is a unary operator.
        Error if the state is not ExpectOperand.
        Push the token to the operator stack.
        Set the state to ExpectOperand.
    If the token is a binary operator.
        Error if the state is not ExpectOperator.
        While there is an operator token at the top of the operator stack and either the current token is left-associative and of lower then or equal precedence to the operator on the stack, or the current token is right associative and of lower precedence than the operator on the stack.
            Pop the operator from the operator stack and push it onto the output queue.
        Push the current operator onto the operator stack.
        Set the state to ExpectOperand. 
    If the token is a Function.
        Error if the state is not ExpectOperand.  
        Push the token onto the operator stack.
        Set the state to ExpectOperand.
    If the token is a open parentheses.
        Error if the state is not ExpectOperand.
        Push the token onto the operator stack.
        Set the state to ExpectOperand.
    If the token is a close parentheses.
         Error if the state is not ExpectOperator.
         Until the token at the top of the operator stack is a left parenthesis.
             Pop the token off of the operator stack and push it onto the output queue.
         Pop the left parenthesis off of the operator stack and discard.
         If the token at the top of the operator stack is a function then pop it and push it onto the output queue.
         Set the state to ExpectOperator.
At this point you have processed all the input tokens.
While there are tokens on the operator stack.
    Pop the next token from the operator stack and push it onto the output queue.
    If a parenthesis is encountered then error.  There are mismatched parenthesis.

前のトークンを見ると、単項演算子と 2 項演算子 (具体的には負の接頭辞と減算演算子について話している) を簡単に区別できます。前のトークンがない場合、前のトークンが左括弧である場合、または前のトークンが演算子である場合は、単項前置演算子に遭遇したことになります。それ以外の場合は、二項演算子に遭遇しました。

于 2015-04-15T13:50:43.717 に答える