1

インフィックスをポストフィックスに変換するアルゴリズムは、ウェブ全体に数多くあります。しかし、私の質問は、機能をサポートするためにそれを作成する方法ですか? たとえば、sin(x+y)*z です。

コードをいただければ幸いです。

4

5 に答える 5

3

関数呼び出しのサポートを含む infix から postfix への変換を提供するアルゴリズムを探している場合は、以下の疑似コード (Python コードのように見えます) を使用できます。私は自分のケースのためにこれを書きましたが、まだ徹底的にテストしていません。バグを見つけたら、私に知らせてください。

私は同じJava実装も書いています。

また、この実装について注意すべき点がいくつかあります。

  1. このアルゴリズムは、infix 内のトークンのストリームを想定しています。式文字列は解析しません。したがって、各トークンは、オペランド、演算子、関数呼び出しなどとして識別できます。

  2. 7 種類のトークンがあります。

    • オペランド X、Y など
    • 左括弧 - (
    • 右括弧 - )
    • 演算子 - +、*
    • 関数呼び出し開始 - sin(
    • 関数呼び出しの終了 - sin( x )
    • コンマ - 、

  3. 関数呼び出しの開始は[アルゴリズム内の文字で示され、関数呼び出しの終了は で示され]ます。)関数呼び出しの終了は、文字列式では同じ文字で表される場合がありますが、右括弧とは異なるトークンであることに注意してください。

  4. すべての演算子は、通常の意味として優先順位と結合性を持つ二項演算子です。

  5. カンマは、 LEFT (+ および * と同じ),の優先順位と結合規則を持つ特別な二項演算子です。NEGATIVE INFINITYコンマ演算子は、関数呼び出しの引数を区切るために使用されます。したがって、関数呼び出しの場合:

    f(a,b,c)

first comma separates a and b
second comma separates a,b and c

So the postfix for the above will be 
ab,c,f

    コンマ演算子は、最初の引数で指定されたリストに 2 番目の引数を追加するリストへの追加関数と見なすことができます。または、両方が単一の値である場合は、2 つの値のリストを作成します。

アルゴリズム

infix_to_postfix(infix):

    postfix = []
    infix.add(')')
    stack = []
    stack.push('(')
    for each token in infix: 
        if token is operand:
            postfix.add(token)
        if token is '[':
            stack.push(token)
        else if token is operator:
            if stack is empty OR 
               stack[top] is '(' or stack[top] is '[':
                stack.push(token)
            else if (operator)token['precedence'] > stack[top]['precedence'] OR
               ( (operator)token['precedence'] == stack[top]['precedence'] AND 
                 (operator)token['associativity') == 'RIGHT' ):
                stack.push(token)     
            else
                postfix.add(stack.pop())
                stack.push(token)
        else if token is '(':
            stack.push(token)
        else if token is ')':            
            while topToken = stack.pop() NOT '(':
                postfix.add(topToken)
        else if token is ']':
            while True:
                topToken = stack.pop()
                postfix.add(topToken)
                if topToken is '[':
                    break

        else if token is ',':
            while topToken = stack.peek() NOT '[':
                postfix.add(topToken)
                stack.pop()
            stack.push(token)
于 2016-01-24T00:34:30.653 に答える
3

それは非常に簡単です。関数でも機能します。使用する通常の演算子 (+、-、​​ など) も関数です。あなたの問題は、あなたが「機能」（sinのような）と見なすものは中置ではなく、接頭辞にあるということです。

問題に戻るには：これらのプレフィックス関数をポストフィックスに変換するだけです（Webでもプレフィックスからポストフィックスを見つける必要があります-「プレフィックス」という用語を知らないと思います）。

EDIT：基本的には、最初に引数を変換して順番に出力し、その後に関数の名前を追加するだけです。

于 2012-07-29T09:47:11.463 に答える
2

自分で解決する必要があるコード。例として特定のケースを使用すると、開始するのに役立つ場合があります。の後置形式は次のsin(x + y) * zようになります。

xy + sin z *

この 1 つの例では、いくつかの操作は 2 つの値 (+と*) で操作され、他の操作は 1 つ ( sin)で操作されることに注意してください。

于 2012-07-29T09:50:10.890 に答える
2

@mickeymoon アルゴリズムは機能しているように見えますが、まだいくつかの調整を行う必要がありました (私には機能しませんでした) ので、誰か別の実装 (Java のような実装) に役立つと思います。https://en.wikipedia.org/wiki/Shunting-yard_algorithmに基づく

Stack<Token> stack = new Stack<>();
List<Token> result = new ArrayList<>();
//https://en.wikipedia.org/wiki/Shunting-yard_algorithm
// with small adjustment for expressions in functions. Wiki example works only for constants as arguments
for (Token token : tokens) {
    if (isNumber(token) || isIdentifier(token)) {
        result.add(token);
        continue;
    }
    if (isFunction(token)) {
        stack.push(token);
        continue;
    }


    // if OP(open parentheses) then put to stack
    if (isOP(token)) {
        stack.push(token);
        continue;
    }
    // CP(close parentheses) pop stack to result until OP
    if (isCP(token)) {
        Token cur = stack.pop();
        while (!isOP(cur)) {
            if (!isComma(cur)) {
                result.add(cur);
            }
            cur = stack.pop();
        }
        continue;
    }
    if (isBinaryOperation(token)) {
        if (!stack.empty()) {
            Token cur = stack.peek();
            while ((!isBinaryOperation(cur)
                    || (isBinaryOperation(cur) && hasHigherPriority(cur, token))
                    || (hasEqualPriority(cur, token) && isLeftAssociative(token)))
                    && !isOP(cur)
            ) {
                // no need in commas in resulting list if we now how many parameters the function need
                if (!isComma(cur)) {
                    result.add(cur);
                }

                stack.pop();
                if (!stack.empty()) {
                    cur = stack.peek();
                }
            }
        }
        stack.push(token);
        continue;
    }

    if (isComma(token)) {
        Token cur = stack.peek();
        while (!(isOP(cur) || isComma(cur))) {
            result.add(cur);
            stack.pop();
            if (!stack.empty()) {
                cur = stack.peek();//  don't pop if priority is less
            }
        }
        stack.push(token);

    }
}
while (!stack.empty()) {
    Token pop = stack.pop();
    if (!isComma(pop)) {
        result.add(pop);
    }

}
return result;

関数合成や複雑な引数を含むさまざまな複雑な式でテストしました（Wikiアルゴリズムの例では機能しません）。いくつかの例 (e は単なる変数、min、max、rand - 関数):

入力: (3.4+2^(5-e))/(1+5/5)

出力: 3.4 2 5 e - ^ + 1 5 / + /

入力: 2+rand(1.4+2, 3+4)

出力: 2 1.4 2 + 3 4 + ランド +

入力:最大(4+4,最小(1*10,2+(3-e)))

出力: 4 4 + 1 10 * 2 3 e - + 最小 最大

また、3つの引数（各引数はそれ自体が式）を持つ複雑な関数でテストしましたが、問題ありません。

これは、トークンのリストを受け取り、後置表記でトークンのリストを返す私のJava 関数の github です。そして、ここに最初の関数からの出力を受け取り、式の値を計算する関数があります

于 2020-03-31T19:02:38.757 に答える
1

同様に、sin、cos などの関数を単項演算子と+見なすことができます。+(x,y)したがって、sin(x+y)*z は と書くことができますx y + sin z *。これらの単項関数を特別に扱う必要があります。

于 2012-07-29T09:49:04.593 に答える