git.gag.com Git - debian/openrocket/blob - core/src/de/congrace/exp4j/InfixTranslator.java

   1 /*
   2    Copyright 2011 frank asseg
   3
   4    Licensed under the Apache License, Version 2.0 (the "License");
   5    you may not use this file except in compliance with the License.
   6    You may obtain a copy of the License at
   7
   8        http://www.apache.org/licenses/LICENSE-2.0
   9
  10    Unless required by applicable law or agreed to in writing, software
  11    distributed under the License is distributed on an "AS IS" BASIS,
  12    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13    See the License for the specific language governing permissions and
  14    limitations under the License.
  15
  16  */
  17 package de.congrace.exp4j;
  18
  19 import java.util.Set;
  20 import java.util.Stack;
  21
  22 /**
  23  * Translate a mathematical expression in human readable infix notation to a
  24  * Reverse Polish Notation (postfix) expression for easier parsing. by
  25  * implementing the shunting yard algorithm by dijkstra
  26  *
  27  * @author fas@congrace.de
  28  */
  29 class InfixTranslator {
  30
  31         private static String substituteUnaryOperators(String expr) {
  32                 final StringBuilder exprBuilder = new StringBuilder(expr.length());
  33                 final char[] data = expr.toCharArray();
  34                 char lastChar = ' ';
  35                 for (int i = 0; i < expr.length(); i++) {
  36                         if (exprBuilder.length() > 0) {
  37                                 lastChar = exprBuilder.charAt(exprBuilder.length() - 1);
  38                         }
  39                         final char c = data[i];
  40                         switch (c) {
  41                         case '+':
  42                                 if (i > 0 && lastChar != '(' && !(OperatorToken.isOperator(lastChar))) {
  43                                         exprBuilder.append(c);
  44                                 }
  45                                 break;
  46                         case '-':
  47                                 if (i > 0 && lastChar != '(' && !(OperatorToken.isOperator(lastChar))) {
  48                                         exprBuilder.append(c);
  49                                 } else {
  50                                         exprBuilder.append('#');
  51                                 }
  52                                 break;
  53                         default:
  54                                 if (!Character.isWhitespace(c)) {
  55                                         exprBuilder.append(c);
  56                                 }
  57                         }
  58                 }
  59                 return exprBuilder.toString();
  60         }
  61
  62         /**
  63          * Delegation method for simple expression without variables or custom
  64          * functions
  65          *
  66          * @param infixExpression
  67          *            the infix expression to be translated
  68          * @return translated RNP postfix expression
  69          * @throws UnparsableExpressionException
  70          *             when the expression is invalid
  71          * @throws UnknownFunctionException
  72          *             when an unknown function has been used in the input.
  73          */
  74         static String toPostfixExpression(String infixExpression) throws UnparsableExpressionException, UnknownFunctionException {
  75                 return toPostfixExpression(infixExpression, null, null);
  76         }
  77
  78         /**
  79          * implement the shunting yard algorithm
  80          *
  81          * @param infixExpression
  82          *            the human readable expression which should be translated to
  83          *            RPN
  84          * @param variableNames
  85          *            the variable names used in the expression
  86          * @param customFunctions
  87          *            the CustomFunction implementations used
  88          * @return the expression in postfix format
  89          * @throws UnparsableExpressionException
  90          *             if the expression could not be translated to RPN
  91          * @throws UnknownFunctionException
  92          *             if an unknown function was encountered
  93          */
  94         static String toPostfixExpression(String infixExpression, String[] variableStrings, Set<CustomFunction> customFunctions)
  95                         throws UnparsableExpressionException, UnknownFunctionException {
  96                 infixExpression = substituteUnaryOperators(infixExpression);
  97                 final Token[] tokens = new Tokenizer(variableStrings, customFunctions).tokenize(infixExpression);
  98                 final StringBuilder output = new StringBuilder(tokens.length);
  99                 final Stack<Token> operatorStack = new Stack<Token>();
 100                 for (final Token token : tokens) {
 101                         token.mutateStackForInfixTranslation(operatorStack, output);
 102                 }
 103                 // all tokens read, put the rest of the operations on the output;
 104                 while (operatorStack.size() > 0) {
 105                         output.append(operatorStack.pop().getValue()).append(" ");
 106                 }
 107                 return output.toString().trim();
 108         }
 109 }