23

私はクラスの JavaScript で Shunting-Yard Algorithm の実装に取り​​組んできました。

これまでの私の仕事は次のとおりです。

var userInput = prompt("Enter in a mathematical expression:");
var postFix = InfixToPostfix(userInput);
var result = EvaluateExpression(postFix);

document.write("Infix: " + userInput + "<br/>");
document.write("Postfix (RPN): " + postFix + "<br/>");
document.write("Result: " + result + "<br/>");


function EvaluateExpression(expression)
{
    var tokens = expression.split(/([0-9]+|[*+-\/()])/);
    var evalStack = [];

    while (tokens.length != 0)
    {
        var currentToken = tokens.shift();

        if (isNumber(currentToken))
        {
            evalStack.push(currentToken);
        }
        else if (isOperator(currentToken))
        {
            var operand1 = evalStack.pop();
            var operand2 = evalStack.pop();

            var result = PerformOperation(parseInt(operand1), parseInt(operand2), currentToken);
            evalStack.push(result);
        }
    }
    return evalStack.pop();
}

function PerformOperation(operand1, operand2, operator)
{
    switch(operator)
    {
        case '+': 
            return operand1 + operand2;
        case '-':
            return operand1 - operand2;
        case '*':
            return operand1 * operand2;
        case '/':
            return operand1 / operand2;
        default:
            return;
    }

}

function InfixToPostfix(expression)
{
    var tokens = expression.split(/([0-9]+|[*+-\/()])/);
    var outputQueue = [];
    var operatorStack = [];

    while (tokens.length != 0)
    {
        var currentToken = tokens.shift();

        if (isNumber(currentToken)) 
        {
            outputQueue.push(currentToken);
        }
        else if (isOperator(currentToken)) 
        {
            while ((getAssociativity(currentToken) == 'left' && 
                    getPrecedence(currentToken) <= getPrecedence(operatorStack[operatorStack.length-1])) ||
                   (getAssociativity(currentToken) == 'right' && 
                    getPrecedence(currentToken) < getPrecedence(operatorStack[operatorStack.length-1]))) 
            {
                outputQueue.push(operatorStack.pop())
            }

            operatorStack.push(currentToken);

        }
        else if (currentToken == '(')
        {
                operatorStack.push(currentToken);
        }
        else if (currentToken == ')')
        {
            while (operatorStack[operatorStack.length-1] != '(')
            {
                if (operatorStack.length == 0)
                    throw("Parenthesis balancing error! Shame on you!");

                outputQueue.push(operatorStack.pop());
            }   
            operatorStack.pop();        
        }   
    }  

    while (operatorStack.length != 0)
    {
        if (!operatorStack[operatorStack.length-1].match(/([()])/))
            outputQueue.push(operatorStack.pop());
        else
            throw("Parenthesis balancing error! Shame on you!");         
    }

    return outputQueue.join(" ");
}    


function isOperator(token)
{
    if (!token.match(/([*+-\/])/))
        return false;
    else 
        return true;
}


function isNumber(token)
{
    if (!token.match(/([0-9]+)/))
        return false;
    else
        return true;
}


function getPrecedence(token)
{
    switch (token)
    {
        case '^':
            return 9; 
        case '*':           
        case '/':
        case '%':
            return 8;
        case '+':
        case '-':
            return 6;
        default: 
            return -1;
    }
}

function getAssociativity(token)
{
    switch(token)
    {
        case '+':
        case '-':
        case '*':
        case '/':
            return 'left';
        case '^':
            return 'right';
    }

}

これまでのところ問題なく動作します。私がそれを与えると：

((5+3) * 8)

次のように出力されます。

インフィックス: ((5+3) * 8) ポストフィックス
(RPN): 5 3 + 8 *
結果: 64

ただし、単項演算子の実装に苦労しているため、次のようなことができます。

(( -5 +3) * 8)

単項演算子 (否定など) を実装する最良の方法は何でしょうか? また、浮動小数点数を処理するための提案はありますか?

最後にもう 1 つ、私が JavaScript で奇妙なことをしているのを見た人がいたら教えてください。これは初めての JavaScript プログラムで、まだ慣れていません。

4

7 に答える 7

14

最も簡単な方法は、浮動小数点数と負数の両方を処理するisNumbermatchを作成することです。/-?[0-9]+(\.[0-9]+)?/

単項演算子 (かっこで囲まれた式の単項否定など) を本当に処理する必要がある場合は、次のことを行う必要があります。

  • それらを右結合にします。
  • どの中置演算子よりも優先順位を高くします。
  • それらを個別に処理します(オペランドを 1 つだけ取るEvaluateExpression別の関数を作成します)。PerformUnaryExpression
  • InfixToPostfixある種の状態を追跡することにより、単項とバイナリのマイナスを区別します。このPython の例で がどのよう'-'に変換されるかを確認してください。'-u'

別の SO questionで単項マイナスの処理のより完全な説明を書きました。

于 2011-03-09T03:18:08.763 に答える
4

私の提案はこれです。「-」を算術演算子として扱わないでください。「符号」演算子として扱います。または、オペランド全体の一部 (つまり、その符号) であるかのように扱います。つまり、「-」に遭遇するたびに、その後のオペランドに -1 を掛けてから、次のトークンの読み取りに進む必要があるということです。:)それが役立つことを願っています。単純な考えですが…

于 2009-10-20T08:46:35.937 に答える
1

これをサポートする必要があるときは、中間段階でこれを行いました。すべての式の語彙素のリストを生成することから始め、次にヘルパー関数を使用して演算子とオペランドを抽出し、「オペランドの取得」関数は単項演算子を検出するたびに単純に 2 つの語彙素を消費しました。

ただし、「単項マイナス」を表すために別の文字を使用すると、非常に役立ちます。

于 2009-10-20T08:48:46.930 に答える
0

私の Java 実装では、次の方法で行いました。

expression = expression.replace(" ", "").replace("(-", "(0-")
                .replace(",-", ",0-");
        if (expression.charAt(0) == '-') {
            expression = "0" + expression;
        }
于 2012-03-12T19:03:41.787 に答える