// Catalano Math Library
// The Catalano Framework
//
// Copyright © Diego Catalano, 2012-2019
// diego.catalano at live.com
//
// Copyright © Andrei Ciobanu, 2010-2019
// gnomemory at yahoo.com
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
//
package Catalano.Math;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* Polish Expression.
* Is a mathematical notation in which operators precede their operands, in contrast to the more common infix notation.
*
* Original implementation: http://andreinc.net/2010/10/05/converting-infix-to-rpn-shunting-yard-algorithm/
* @author Diego Catalano
*/
public class PolishExpression {
/**
* Specifies the associativity.
*/
public static enum Associativity{
/**
* Left association.
*/
Left,
/**
* Right association.
*/
Right
}
private static int LEFT = 0;
private static int RIGHT = 1;
private static final Map OPERATORS = new HashMap();
static {
// Map<"token", []{precendence, associativity}>
OPERATORS.put("+", new int[] { 0, LEFT });
OPERATORS.put("-", new int[] { 0, LEFT });
OPERATORS.put("*", new int[] { 1, LEFT });
OPERATORS.put("/", new int[] { 1, LEFT });
OPERATORS.put("%", new int[] { 1, LEFT });
OPERATORS.put("mod", new int[] { 1, LEFT });
OPERATORS.put("abs", new int[] { 1, RIGHT });
OPERATORS.put("ln", new int[] { 1, RIGHT });
OPERATORS.put("sin", new int[] { 1, RIGHT });
OPERATORS.put("cos", new int[] { 1, RIGHT });
OPERATORS.put("sum", new int[] { 1, RIGHT });
OPERATORS.put("^", new int[] { 2, RIGHT });
OPERATORS.put("pow", new int[] { 2, RIGHT });
}
/**
* Initializes a new instance of the PolishExpression class.
*/
public PolishExpression() {}
/**
* Add a operator into polish expression.
* @param symbol Symbol.
* @param precedence Precedence.
* @param associativity Associativity.
*/
public void AddOperator(String symbol, int precedence, Associativity associativity){
switch(associativity){
case Left:
OPERATORS.put(symbol, new int[] {precedence, 0});
break;
case Right:
OPERATORS.put(symbol, new int[] {precedence, 1});
break;
}
}
/**
* Evaluate the RPN expression.
* @param rpn RPN expression.
* @return The result from the expression.
*/
public double Evaluate(String rpn){
return Evaluate(rpn.split(" "));
}
/**
* Evaluate the RPN expression.
* @param rpnTokens RPN tokens.
* @return The result from the expression.
*/
public double Evaluate(String[] rpnTokens){
Stack values = new Stack<>();
double result = 0;
for (int i = 0; i < rpnTokens.length; i++) {
if(Tools.isNumeric(rpnTokens[i])){
values.push(Double.parseDouble(rpnTokens[i]));
} else{
result = Calc(values, rpnTokens[i]);
}
}
return result;
}
private static double Calc(Stack values, String op){
switch (op) {
case "+":
{
Double a = values.pop();
Double b = values.pop();
values.push(b+a);
return values.peek();
}
case "-":
{
Double a = values.pop();
Double b = values.pop();
values.push(b-a);
return values.peek();
}
case "*":
{
Double a = values.pop();
Double b = values.pop();
values.push(b*a);
return values.peek();
}
case "/":
{
Double a = values.pop();
Double b = values.pop();
values.push(b/a);
return values.peek();
}
case "^":
{
Double a = values.pop();
Double b = values.pop();
values.push(Math.pow(b, a));
return values.peek();
}
case "pow":
{
Double a = values.pop();
Double b = values.pop();
values.push(Math.pow(b, a));
return values.peek();
}
case "ln":
{
Double a = values.pop();
values.push(Math.log(a));
return values.peek();
}
case "exp":
{
Double a = values.pop();
values.push(Math.exp(a));
return values.peek();
}
case "sqrt":
{
Double a = values.pop();
values.push(Math.sqrt(a));
return values.peek();
}
case "sin":
{
Double a = values.pop();
values.push(Math.sin(a));
return values.peek();
}
case "cos":
{
Double a = values.pop();
values.push(Math.cos(a));
return values.peek();
}
case "tan":
{
Double a = values.pop();
values.push(Math.tan(a));
return values.peek();
}
default:
break;
}
return 0;
}
/**
* Convert Infix notation to RPN.
* @param infixNotation Infix notation.
* @return RPN.
*/
public String toReversePolishNotation(String infixNotation){
String[] tokens = toReversePolishNotation(infixNotation.split(" "));
return Arrays.toString(tokens);
}
/**
* Convert Infix notation to RPN.
* @param inputTokens Infix tokens.
* @return RPN.
*/
public String[] toReversePolishNotation(String[] inputTokens) {
ArrayList out = new ArrayList<>();
Stack stack = new Stack<>();
// For all the input tokens [S1] read the next token [S2]
for (String token : inputTokens) {
if (isOperator(token)) {
// If token is an operator (x) [S3]
while (!stack.empty() && isOperator(stack.peek())) {
// [S4]
if ((isAssociative(token, LEFT) && cmpPrecedence(token, stack.peek()) <= 0) || (isAssociative(token, RIGHT) && cmpPrecedence(token, stack.peek()) < 0)) {
out.add(stack.pop()); // [S5] [S6]
continue;
}
break;
}
// Push the new operator on the stack [S7]
stack.push(token);
} else if (token.equals("(")) {
stack.push(token); // [S8]
} else if (token.equals(")")) {
// [S9]
while (!stack.empty() && !stack.peek().equals("(")) {
out.add(stack.pop()); // [S10]
}
stack.pop(); // [S11]
} else {
out.add(token); // [S12]
}
}
while (!stack.empty()) {
out.add(stack.pop()); // [S13]
}
String[] output = new String[out.size()];
return out.toArray(output);
}
/**
* Test if a certain is an operator .
* @param token The token to be tested .
* @return True if token is an operator . Otherwise False .
*/
private static boolean isOperator(String token) {
return OPERATORS.containsKey(token);
}
/**
* Test the associativity of a certain operator token .
* @param token The token to be tested (needs to operator).
* @param type LEFT_ASSOC or RIGHT_ASSOC
* @return True if the tokenType equals the input parameter type .
*/
private static boolean isAssociative(String token, int type) {
if (!isOperator(token)) {
throw new IllegalArgumentException("Invalid token: " + token);
}
if (OPERATORS.get(token)[1] == type) {
return true;
}
return false;
}
/**
* Compare precendece of two operators.
* @param token1 The first operator .
* @param token2 The second operator .
* @return A negative number if token1 has a smaller precedence than token2,
* 0 if the precendences of the two tokens are equal, a positive number
* otherwise.
*/
private static int cmpPrecedence(String token1, String token2) {
if (!isOperator(token1) || !isOperator(token2)) {
throw new IllegalArgumentException("Invalied tokens: " + token1 + " " + token2);
}
return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
}
}
Ads help maintain this website.