调车场算法解析函数参数

Question

我正在努力让调车场算法的实现工作。它适用于数字和运算符。但是当我尝试向输入添加功能时出现问题。因为函数参数输出到函数的左边，而它应该输出到右边。

测试程序

public class FrontTest
{
    public static void main(String[] args)
    {
        String str = "cbrt ( 8 )";
        System.out.println(ShuntTest.infixToPostfix(str));
    }
}

算法

import java.util.*;

public class ShuntTest
{
    public static String infixToPostfix(String infixStr)
    {
        Stack<String> operators = new Stack<String>();
        Queue<String> output = new LinkedList<String>();
        String[] tokens = infixStr.split("[\s]");
        StringBuilder postfixStr = new StringBuilder();
        int tokensRemaining = tokens.length;

        final String PAREN_LEFT = "[\(]";
        final String PAREN_RIGHT = "[\)]";
        final String FUNCTION_ARGSEP = "[\;]";

        for (int i = 0; i < tokens.length; i++)
        {
            if (isNumber(tokens[i]))
            {
                output.offer(tokens[i]);
            }
            else if (isFunction(tokens[i]))
            {
                operators.push(tokens[i]);
            }
            else if (tokens[i].matches(FUNCTION_ARGSEP))
            {
                while (!operators.empty() && operators.peek().matches(PAREN_RIGHT))
                {
                    output.offer(operators.pop());
                    if (operators.empty() && !operators.peek().matches(PAREN_RIGHT))
                    {
                        throw new RuntimeException("Mismatched Parentheses.");
                    }
                }
            }
            else if (isOperator(tokens[i]))
            {
                while (!operators.empty() && ((isOperator(operators.peek())
                        && ((isLeftAssociative(tokens[i]) == true && ((operatorPrecedence(tokens[i]) <= operatorPrecedence(operators.peek()))
                        || ((isLeftAssociative(tokens[i]) == false && ((operatorPrecedence(tokens[i]) < operatorPrecedence(operators.peek())))))))))))
                {
                    output.offer(operators.pop());
                }
                operators.push(tokens[i]);
            }
            else if (!operators.empty() && tokens[i].matches(PAREN_LEFT))
            {
                operators.push(tokens[i]);
            }
            else if (!operators.empty() && tokens[i].matches(PAREN_RIGHT))
            {
                while (!operators.empty() && !operators.peek().matches(PAREN_LEFT))
                {
                    output.offer(operators.pop());
                }
                if (!operators.empty())
                    {
                        operators.pop();
                    }
                else if (!operators.empty() && isFunction(operators.peek()))
                {
                    output.offer(operators.pop());
                }
                else if (operators.empty())
                {
                    throw new RuntimeException("Mismatched Parentheses.");
                }
            }
            tokensRemaining--;
        }

        if (tokensRemaining == 0)
        {
            while (!operators.empty())
            {
                if (operators.peek().matches(PAREN_LEFT)
                        || operators.peek().matches(PAREN_RIGHT))
                {
                    throw new RuntimeException("Mismatched Parentheses.");
                }
                output.offer(operators.pop());
            }
        }

        while (!output.isEmpty())
        {
            while (output.size() > 1)
            {
                postfixStr.append(output.poll() + " ");
            }
            postfixStr.append(output.poll());
        }
        return postfixStr.toString();
    }

    public static boolean isNumber(String str)
    {
        final String NUMBER = "^0?-?\+?\d+(\.\d+)?$";
        return str.matches(NUMBER) ? true : false;
    }

    public static boolean isOperator(String str)
    {
        switch (str)
        {
            case "^":   
            case "/":
            case "*":
            case "+":
            case "-":
                return true;
            default:
                return false;
        }
    }

    private static boolean isLeftAssociative(String str)
    {
        switch (str)
        {
            case "^":   
                return false;   
            case "/":
            case "*":
            case "+":
            case "-":
                return true;
            default:
                throw new IllegalArgumentException("Operator unknown: " + str);
        }   
    }

    private static int operatorPrecedence(String str)
    {
        switch (str)
        {
            case "^":
                return 4;
            case "/":
            case "*":
                return 3;
            case "+":
            case "-":
                return 2;
            default:
                throw new IllegalArgumentException("Operator unknown: " + str);
        }   
    }

    public static boolean isFunction(String str)
    {
        switch (str)
        {   
            case "sin": 
            case "cos":
            case "tan":
            case "sqrt":
            case "cbrt":
            case "root_of":
                return true;
            default:
                return false;
        }   
    }
}

示例 1：

输入：cbrt ( 8 )

输出：8 cbrt

输出应该是：cbrt 8

示例 2：

输入：cbrt ( 8 ) + sqrt ( 9 )

输出：8 9 sqrt + cbrt

输出应该是：cbrt 8 sqrt 9 +

示例 3：

输入：5 + 4 - 9 / 2 ^ 6 * cbrt ( 8 )

输出：5 4 + 9 2 6 ^ / 8 cbrt * -

输出应该是：5 4 + 9 2 6 ^ / cbrt 8 * -

Answer 1

想一想。调车场算法将中缀转换为后缀。然而这个：

cbrt ( 8 )

不是中缀表达式。它是一个 prefix 表达式。

作为后缀表达式，它看起来像这样：

8  cbrt

中缀表达式的样子留作 reader 的练习，但这不是您开始的内容。

调车场算法解析函数参数

Shunting-yard algorithm parsing function agruments

java

algorithm

rpn

postfix-notation

shunting-yard