How to parse a calculator input string

Question

I'm writing a calculator, and when the user hits enter, I need it to find anywhere that there are parentheses for example.

Then I need the calculator to solve the math inside those first.

What would be the best way to get the functions inside the parentheses and set the value of a second String as whatever is inside the parentheses?

Answer 1

Here is a recursive descent parser for a subset of the grammar on the Wikipedia page on recursive descent parsers that seems relevant for your case.

I haven't included a tokenizer, but it should be fairly straightforward to write one that suits the interface. The code isn't significantly different to what is on the Wikipedia page, with the exception that only implements a subset of the grammar, and it actually performs the calculations.

/**
 * From http://en.wikipedia.org/wiki/Recursive_descent_parser
 *
 * expression =
 *     [ "+" | "-" ] term { ("+" | "-") term } .
 *
 * term =
 *     factor { ( "*" | "/" ) factor } .
 *
 * factor =
 *     number
 *     | "(" expression ")" .
 */
public class Arithmetic
{
  private final TokenStream tokenStream;
  private TokenStream.Token currentToken;
  private double currentValue;

  public Arithmetic(TokenStream tokenStream) {
    this.tokenStream = tokenStream;
  }

  public double parse() {
    nextToken();
    return expression();
  }

  private double expression() {
    double lhs = 0.0;
    if (accept(TokenStream.Token.MINUS)) {
      lhs = -term();
    } else {
      // Optional unary plus swallowed
      accept(TokenStream.Token.PLUS);
      lhs = term();
    }
    for (boolean moreTerms = true; moreTerms; ) {
      if (accept(TokenStream.Token.PLUS)) {
        lhs += term();
      } else if (accept(TokenStream.Token.MINUS)) {
        lhs -= term();
      } else {
        moreTerms = false;
      }
    }
    return lhs;
  }

  private double term() {
    double lhs = factor();
    for (boolean moreFactors = true; moreFactors; ) {
      if (accept(TokenStream.Token.TIMES)) {
        lhs *= factor();
      } else if (accept(TokenStream.Token.DIVIDED_BY)) {
        lhs /= factor();
      } else {
        moreFactors = false;
      }
    }
    return lhs;
  }

  private double factor() {
    if (peek(TokenStream.Token.NUMBER)) {
      // Save currentValue before calling nextToken()
      double value = currentValue;
      nextToken();
      return value;
    }
    require(TokenStream.Token.OPEN);
    double value = expression();
    require(TokenStream.Token.CLOSE);
    return value;
  }

  private void nextToken() {
    currentToken = tokenStream.nextToken();
    if (currentToken == TokenStream.Token.NUMBER) {
      currentValue = tokenStream.getValue();
    }
  }

  private boolean peek(TokenStream.Token token) {
    return (currentToken == token);
  }

  private boolean accept(TokenStream.Token token) {
    if (peek(token)) {
      nextToken();
      return true;
    }
    return false;
  }

  private void require(TokenStream.Token token) {
    if (currentToken == token) {
      nextToken();
    } else {
      throw new IllegalStateException("Unexpected token " + currentToken);
    }
  }

}

The interface for TokenStream is pretty simple:

public interface TokenStream {
  public enum Token {
    // Terminals
    PLUS,
    MINUS,
    TIMES,
    DIVIDED_BY,
    OPEN,
    CLOSE,
    NUMBER,
    EOF
  }

  Token nextToken();

  // Retrieve value when nextToken() returns NUMBER
  double getValue();
}

---

Another possibility is to use the scripting facilities to evaluate some JavaScript like so:

  try
  {
    ScriptEngineManager factory = new ScriptEngineManager();
    ScriptEngine engine = factory.getEngineByName("JavaScript");
    Object result = engine.eval("1 + 2 / 2");
    System.out.println(result.getClass().getCanonicalName());
    System.out.println(result);
  }
  catch (ScriptException e)
  {
    e.printStackTrace();
  }

Answer 2

As an alternative, you can have Java compile itself. It's limited to simple operations such as + - / *

Full working example:

import java.lang.*;
import java.io.*;

public class SO {
  public static void main(String[] args) {
    try { System.out.println(calculate("5 * (1 + 1)")); }
    catch (Exception e) { System.out.println("we tried " + e); }
  }

  private static String subProc(String command) throws Exception {
    Process proc = Runtime.getRuntime().exec(command); // kick off sub process
    BufferedReader stdout = new BufferedReader(new
      InputStreamReader(proc.getInputStream())); // read from stdout
    StringBuilder sb = new StringBuilder(); // build output
    String ln = stdout.readLine(); // read lines, until we are at the end
    while (ln != null) { sb.append(ln); ln = stdout.readLine(); }
    proc.waitFor(); // wait for process to exit
    int exitCode = proc.exitValue(); // get exit code
    if (exitCode != 0) // if it isn't 0, something went wrong. Throw error
      throw new Exception("invalid math! exited with code: " + exitCode);
    return sb.toString(); // return stdout
  }

  private static String calculate(String math) throws Exception {
    //** Compile a new Java class that will spit out the calculation
    File file = File.createTempFile("tmp", ".java"); // create new temp file
    String classpath = file.getParent(), // get class path, and name
    classname = file.getName().substring(0, file.getName().length() - 5);
    PrintWriter writer = new PrintWriter(file); // write Java to temp file
    writer.println(
      "public class " + classname + "{" +
        "public static void main(String[] args) { " +
          "System.out.println(" + math + "); }}"); writer.close();
    subProc("javac " + file.getAbsolutePath()); // compile it
    file.delete(); // remove our source file
    return subProc("java -cp " + classpath + " " + classname); // run it
  }
}

Compile and run as usual:

javac SO.java; java SO

In this particular example, it will print out 10 as the call was calculate("5 * (1 + 1)"));

This isn't a practical approach to the problem speed-wise, but it is a pure Java solution that I had fun with.

Answer 3

You could use a stack:

1. Push characters onto stack until )
2. Then to get your sub equation pop off the stack until a (
3. Push result of equation from step 2 onto stack
4. Repeat until no parentheses found then solve final equation

Answer 4

I liked the first two poster's ideas, so here's my approach:

1) Place character into a stack. When you see a ) you pop members off of the stack until you see (. When finished, you pop off all of the characters and place them into another String or StringBuffer or StringBuilder in the reverse order.

2) Split the rest of the equation by reverse precedence. Then for each higher level of operator precedence, you split the sub-equations by that operator.

3) Then when you're at the highest level (e.g. exponents), you then solve for all of those. Then proceed to the lower level of operators.

Answer 5

You have some different ways to solve this,

1. define a global variable, when user push one of the operand (+,-,*/) you save it in define variable.
2. split string, if you look at whole input as a string, you can split that with one of the defined operand (+,-,*/), then you have an array of operators and operand.
3. use regex, you can use regex to find out what operators and operand.