Алгоритм анализа алгоритмов шунгового двора агенты

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) 

не является выражением инфикса. Это префикс .

Как выражение постфикса это будет выглядеть следующим образом:

8 cbrt 

Что это может выглядеть как выражение инфикс остается в качестве упражнения для читателя, но это не то, что вы начали с.