Skip to content

Instantly share code, notes, and snippets.

@hetelek
Last active February 24, 2022 20:28
Show Gist options
  • Save hetelek/5373189 to your computer and use it in GitHub Desktop.
Save hetelek/5373189 to your computer and use it in GitHub Desktop.
Classes that tokenize, parse and solve math equations. Solving is currently very simple, and cannot factor, complete the square, etc...
import java.util.Arrays;
import java.util.Stack;
import java.util.LinkedList;
enum TokenType
{
OPERATOR, RIGHT_PARENTHESE, LEFT_PARENTHESE, NUMBER, EQUALS, UNKNOWN
}
class Token
{
private String value;
private TokenType type;
public Token(String value, TokenType type)
{
this.value = value;
this.type = type;
}
public Token(char value, TokenType type)
{
this.value = String.valueOf(value);
this.type = type;
}
public static boolean isValidOperator(char currentChar)
{
switch (currentChar)
{
case '+':
case '-':
case '/':
case '*':
case '^':
return true;
default:
return false;
}
}
public TokenType getType()
{
return type;
}
public String getValue()
{
return value;
}
public int getStrength()
{
if (type == TokenType.OPERATOR)
{
switch (value.charAt(0))
{
case '+':
case '-':
return 1;
case '/':
case '*':
return 2;
case '^':
case 'r':
return 3;
default:
return -1;
}
}
else if (type == TokenType.RIGHT_PARENTHESE || type == TokenType.LEFT_PARENTHESE)
return 4;
return -1;
}
public int getOperandCount()
{
switch (value.charAt(0))
{
case '^':
case 'r':
case '+':
case '-':
case '/':
case '*':
return 2;
default:
return -1;
}
}
public Token getOpposite()
{
switch (value.charAt(0))
{
case '+':
return new Token("-", TokenType.OPERATOR);
case '-':
return new Token("+", TokenType.OPERATOR);
case '/':
return new Token("*", TokenType.OPERATOR);
case '*':
return new Token("/", TokenType.OPERATOR);
case '^':
return new Token("root", TokenType.OPERATOR);
default:
return null;
}
}
public double calculate(double[] args)
{
if (args.length < 1)
return 0;
double answer = args[0];
for (int i = 1; i < args.length; i++)
{
switch (value.charAt(0))
{
case '^':
answer = Math.pow(args[i], answer);
break;
case '+':
answer += args[i];
break;
case '-':
answer = args[i] - answer;
break;
case '/':
answer = args[i] / answer;
break;
case '*':
answer *= args[i];
break;
case 'r':
answer = Math.pow(args[i], 1.0 / answer);
break;
}
}
return answer;
}
}
class Postfix
{
public static double calculateResult(Token[] tokens)
{
Stack<Token> stack = new Stack<Token>();
for (Token token : tokens)
{
if (token.getType() == TokenType.NUMBER)
stack.push(token);
else if (token.getType() == TokenType.OPERATOR)
{
double[] args = new double[token.getOperandCount()];
for (int i = 0; i < args.length; i++)
args[i] = Double.parseDouble(stack.pop().getValue());
double answer = token.calculate(args);
stack.push(new Token(Double.toString(answer), TokenType.NUMBER));
}
}
return Double.parseDouble(stack.pop().getValue());
}
public static double solveForVariable(Token[][] tokens)
{
Stack<Token> stack = new Stack<Token>();
LinkedList<Token> side1 = null;
LinkedList<Token> side2 = null;
for (int i = 0; i < tokens[0].length; i++)
if (tokens[0][i].getType() == TokenType.UNKNOWN)
{
side1 = new LinkedList<Token>(Arrays.asList(tokens[0]));
side2 = new LinkedList<Token>(Arrays.asList(tokens[1]));
break;
}
if (side1 == null)
{
side1 = new LinkedList<Token>(Arrays.asList(tokens[1]));
side2 = new LinkedList<Token>(Arrays.asList(tokens[0]));
}
while (side1.size() > 1 || stack.size() > 0)
{
Token token = side1.removeFirst();
if (token.getType() == TokenType.NUMBER || token.getType() == TokenType.UNKNOWN)
{
stack.push(token);
}
else if (token.getType() == TokenType.OPERATOR)
{
boolean containsUnknown = false;
Token[] args = new Token[token.getOperandCount()];
for (int x = 0; x < args.length; x++)
{
Token currentToken = stack.pop();
if (currentToken.getType() == TokenType.UNKNOWN)
containsUnknown = true;
args[x] = currentToken;
}
if (!containsUnknown)
{
double[] argValues = new double[args.length];
for (int x = 0; x < argValues.length; x++)
argValues[x] = Double.parseDouble(args[x].getValue());
double answer = token.calculate(argValues);
side1.addFirst(new Token(Double.toString(answer), TokenType.NUMBER));
}
else
{
Token[] side2New = new Token[args.length - 1];
for (int y = 0, x = 0; y < args.length; y++)
{
if (args[y].getType() == TokenType.UNKNOWN)
side1.addFirst(args[y]);
else
side2New[x++] = args[y];
}
for (Token newToken : side2New)
side2.addLast(newToken);
side2.addLast(token.getOpposite());
}
}
}
return calculateResult(side2.toArray(new Token[side2.size()]));
}
}
class Tokenizer
{
private String input;
private LinkedList<Token> tokens = new LinkedList<Token>();
public Tokenizer(String input)
{
this.input = input;
}
public LinkedList<Token> getTokens()
{
StringBuilder currentlyBuilt = new StringBuilder();
TokenType lastType = null;
boolean checkForOthers = true;
boolean currentlyNoDecimals = true;
for (int i = 0; i < input.length(); i++)
{
char currentChar = input.charAt(i);
if (Character.isDigit(currentChar) || (lastType != TokenType.NUMBER && currentChar == '-') || (currentChar == '.' && currentlyNoDecimals))
{
if (currentChar == '.')
currentlyNoDecimals = false;
checkForOthers = false;
currentlyBuilt.append(currentChar);
lastType = TokenType.NUMBER;
}
else if (lastType == TokenType.NUMBER)
{
currentlyNoDecimals = true;
tokens.add(new Token(currentlyBuilt.toString(), TokenType.NUMBER));
currentlyBuilt.delete(0, currentlyBuilt.length());
}
if (checkForOthers)
{
if (currentChar == ')')
lastType = TokenType.RIGHT_PARENTHESE;
else if (currentChar == '(')
lastType = TokenType.LEFT_PARENTHESE;
else if (Token.isValidOperator(currentChar))
lastType = TokenType.OPERATOR;
else if (currentChar == '=')
lastType = TokenType.EQUALS;
else
lastType = TokenType.UNKNOWN;
tokens.add(new Token(currentChar, lastType));
}
checkForOthers = true;
}
if (currentlyBuilt.length() > 0)
tokens.add(new Token(currentlyBuilt.toString(), TokenType.NUMBER));
return tokens;
}
}
class Precedence extends Tokenizer
{
Stack<Token> stack = new Stack<Token>();
LinkedList<LinkedList<Token>> finalQueue = new LinkedList<LinkedList<Token>>();
public Precedence(String input)
{
super(input);
}
private void populateStackAndQueue()
{
LinkedList<Token> outputQueue = new LinkedList<Token>();
for (Token token : super.getTokens())
{
if (token.getType() == TokenType.NUMBER || token.getType() == TokenType.UNKNOWN)
outputQueue.add(token);
else if (token.getType() == TokenType.OPERATOR)
{
while (!stack.isEmpty() && stack.peek().getType() == TokenType.OPERATOR && token.getStrength() <= stack.peek().getStrength())
outputQueue.add(stack.pop());
stack.push(token);
}
else if (token.getType() == TokenType.LEFT_PARENTHESE)
stack.push(token);
else if (token.getType() == TokenType.RIGHT_PARENTHESE)
{
while (!stack.isEmpty() && stack.peek().getType() != TokenType.LEFT_PARENTHESE)
outputQueue.add(stack.pop());
if (!stack.isEmpty())
stack.pop();
}
else if (token.getType() == TokenType.EQUALS)
{
while (!stack.isEmpty())
outputQueue.add(stack.pop());
finalQueue.add(outputQueue);
outputQueue = new LinkedList<Token>();
}
}
while (!stack.isEmpty())
outputQueue.add(stack.pop());
finalQueue.add(outputQueue);
}
public Token[][] toPostfix()
{
populateStackAndQueue();
Token[][] tokens = new Token[finalQueue.size()][];
for (int i = 0; i < finalQueue.size(); i++)
tokens[i] = finalQueue.get(i).toArray(new Token[finalQueue.get(i).size()]);
return tokens;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment