How to create java arithmetic calculator with recursion

Question

I need to make a java program that evaluates an expression from an input file and returns the result in an output file. It needs to consider operator precedence, unary and binary operators, bracket matching, and has to rely on recursion only (no stacks or queues).

I've been thinking about this all night, and it frustrates me. I'm not asking for an entire java program written for me. I just need some guidance. I started by writing some pseudo-code, but I don't think it's any good:

Input: the text file to read each expression from. Output: the text file that repeats each expression, as well as printing the result.

Algorithm SecondCalc()
{
   input = “expressions.txt”;
   output = “out.txt”;
   if (input.currentLine has something)
   {
       line = input.currentLine;
       output.write(line);
       line = line.replace(“-space-”, “”);
       evaluate(line);
       //...to be continued
   }
}

Algorithm evaluate(line)
{
  for(i = 0 to line.length)
  {
     if(i == “(” or “)” ) exit loop;
     if(i == “!”) exit loop;
     if(i == “^”) exit loop;
     if(i == “*” or “/” ) exit loop;
     if(i == “+” or “-” ) exit loop;
     if(i == “>” or “>=” or “<” or “<=” ) exit loop;
     if(i == “==” or “!=” ) exit loop;
     if(i == “$”) exit loop;
 }

 temp1 = line from index 0 to i;
 temp2 = line from index i + 1 to line.length;
 if(i == “!”) then evaulate(temp1!);
 //...to be continued
}

Any tips would be appreciated. Thanks.

score 1 · Answer 1 · answered Feb 12 '16 at 03:27

I would suggest reading up on polish notation. It's a good way to store mathematical functions. For instance + cos a b -> cos(a) + b whereas cos + a b -> cos(a+b). There is no ambiguity. Additionally, terms to the right have precedence over terms to the left.

I wrote a symbolic logic manipulator long ago, and reading the strings is definitely hard. Here is what I would suggest for flow:

Look for binary operators that are outside of any parentheses. Start at the highest order of operations and work down.
When you find a binary operator, recursively call the stringtofunction on the arguments to either side of the binary operator. Anything between the binary operator you are looking at and any other binary operator outside parentheses or between the binary operator and the ends of the string counts as 1 object.
The return from part two goes into something like operator return1 return2 in polish notation.
When the outermost sides of the string are parentheses peel them off.
If you did not find any top level binary operators search for unary operators. Recursively call the argument of the unary operator and store it as operator return;

score 1 · Accepted Answer · answered Feb 12 '16 at 04:11

well the first thing I notice is that you say want operator precedence but in your evaluate you ignore operator precedence by essentially doing first come first serve which treats them all with the same precedence. If your aim indeed is to simulate operator precedence (i assume the input is expected to look like java's expressions) then i suggest you either properly process certain operators first before you process others, or you re-arrange the input properly to match other styles like polish notation.

For both cases, i would do a similar process: instead of if statement after if statement in the for loop like you have now, try for loop after for loop where each for loop looks for a specific operator and "does something".

for(i = 0 to line.length)
{
    if(i == “(” or “)” ) doSomething;
}
for(i = 0 to line.length)
{
    if(i == “!” ) doSomething;
}
for(i = 0 to line.length)
{
    if(i == “^”) doSomething;
}
for(i = 0 to line.length)
{
    if(i == “*” or “/” ) doSomething;
}
for(i = 0 to line.length)
{
    if(i == “+” or “-” ) doSomething;
}
for(i = 0 to line.length)
{
    if(i == “>” or “>=” or “<” or “<=” ) doSomething;
}
for(i = 0 to line.length)
{
    if(i == “==” or “!=” )doSomething;
}
for(i = 0 to line.length)
{
    if(i == “$”)doSomething;
}

}

There's much to improve on, but hopefully this points you in the right direction.

How to create java arithmetic calculator with recursion

2 Answers2