2 Copyright 2011 frank asseg
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
8 http://www.apache.org/licenses/LICENSE-2.0
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.
17 package de.congrace.exp4j;
20 import java.util.Stack;
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
27 * @author fas@congrace.de
29 class InfixTranslator {
31 private static String substituteUnaryOperators(String expr) {
32 final StringBuilder exprBuilder = new StringBuilder(expr.length());
33 final char[] data = expr.toCharArray();
35 for (int i = 0; i < expr.length(); i++) {
36 if (exprBuilder.length() > 0) {
37 lastChar = exprBuilder.charAt(exprBuilder.length() - 1);
39 final char c = data[i];
42 if (i > 0 && lastChar != '(' && !(OperatorToken.isOperator(lastChar))) {
43 exprBuilder.append(c);
47 if (i > 0 && lastChar != '(' && !(OperatorToken.isOperator(lastChar))) {
48 exprBuilder.append(c);
50 exprBuilder.append('#');
54 if (!Character.isWhitespace(c)) {
55 exprBuilder.append(c);
59 return exprBuilder.toString();
63 * Delegation method for simple expression without variables or custom
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.
74 static String toPostfixExpression(String infixExpression) throws UnparsableExpressionException, UnknownFunctionException {
75 return toPostfixExpression(infixExpression, null, null);
79 * implement the shunting yard algorithm
81 * @param infixExpression
82 * the human readable expression which should be translated to
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
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);
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(" ");
107 return output.toString().trim();