4

I'm having a lot of trouble trying to do this for some reason. I have a class which wants me to evaluate a complex Java expression such as (3 + 5[3*2-4]), using recursion. I think I have an idea on how I want to approach it, but I can't seem to figure out how to solve something really simple first off - like

5-2*10

I have no clue how to do that. They don't allow you to import any outside scripts, nor are you allowed to convert it to a postfix expression.

I don't expect anybody to write me the code but if anybody could send me off in the right direction or give me a little psuedocode I'd really appreciate it - I've spent like two hours to no avail trying to understand how I could use string tokenizers and other stuff to solve it, but I always run into a wall that I don't know how to get around. Thanks a lot in advance!

Mikey Chen
  • 2,370
  • 1
  • 19
  • 31
  • I suggest you start by reading one character at a time and parsing it. This will give you a start. Do it without operator precedence and then adding precedence just involves using recursion. – Peter Lawrey Oct 07 '14 at 20:28
  • Throw characters on a stack. Evaluate each character off the top of the stack for what to do next. I'll run it through my head and see if I can get a sane example. – Compass Oct 07 '14 at 20:29
  • 1
    @Compass Using your own stack would avoid having to use recursion (i.e. the thread's stack) I am not sure it's easier though. – Peter Lawrey Oct 07 '14 at 20:30
  • 1
    @PeterLawrey Well, at a rough programming level, I guess. Anything in parentheses or brackets gets evaluated by calling the method on just that subsection, and the value is passed up. I'm having a hard time describing it without writing pseudocode. I'll write some later maybe. This is one of those things that is interesting to think about. – Compass Oct 07 '14 at 20:32
  • @Compass correct and `)` does a return or pops off the stack. – Peter Lawrey Oct 07 '14 at 20:33
  • Hint: Recursion is like postfix. – Hot Licks Oct 07 '14 at 20:34
  • Also, in this case, `5-2*10` <- do we use order of operations? Will drastically change how this program works! Like, do we treat this as an old school calculator where 5-2*10 = 30 or a graphing calc where 5-2*10 = -15? – Compass Oct 07 '14 at 20:36
  • [duplicate](http://stackoverflow.com/q/4173623/1113392) of [duplicate](http://stackoverflow.com/q/15173681/1113392) – A4L Oct 07 '14 at 20:38
  • I have to follow PEMDAS, sadly. – Mikey Chen Oct 08 '14 at 01:40

4 Answers4

0

You could consecutively reduce sub-expressions (so called "redexes") until no more reductions are possible.

This replacement of inner expressions can be done with regular expressions:

  1. "(\d+)([*/])(-?\d+)"
  2. "(\d+)([+-])(-?\d+)"
  3. "\[(-?\d+)\]"
  4. ...

Loops in loops. See Pattern, Matcher, find.

As this seems homework, I leave the further challenge to you.

Negative numbers may be a bit challenging, might try a unary minus operator.

Joop Eggen
  • 107,315
  • 7
  • 83
  • 138
0

Back at university, I had to do this as well.

The approach I took was to parse expressions using recursive descent. The article does a great job of providing an overview of how your parser should tokenize your input, that you can then go on to evaluate. The key you have to realize here, is that making your parser be top-down is going to make your life easier beacuse if you were to start at the bottom of the parse tree with individual characters and then use the rules to connect the characters together into larger tokens as we go is going to require you to maintain a stack and get overly complicated. As appose to this, since you know all you're doing are logical operations, you can firstly assume that your expression matches your production rules and then you can go on to look at the internal logical implications of this assumption.

These Brief Notes on Parsing actually explain very well the difference in implementations if you were to choose to build a top-down parser or a bottom-up parser. However, depending on how complex the expressions your parser needs to handle, you might choose to implement a bottom-up parser, because for all their complexities, bottomup parsing algorithms are more powerful than top-down.

The parser I built was in OCaml, and functional programming turned out to be quite a good solution for this use case.

Please let me know if you have any questions!

Devarsh Desai
  • 5,984
  • 3
  • 19
  • 21
  • I have no experience programmng with grammars or tokens. Do you think this is the only viable path for me to follow, or is there any other beginner-friendly solution? I'm watching tons of videos on recursive descent parsing but I can't seem to grasp it. EDIT: Also it seems that my professor isn't allowing us to create any new classes, so I can't make a token class. Does that mean I can't implement recursive descent? – Mikey Chen Oct 08 '14 at 02:40
  • hey henderswan, it took me a while to recollect an algorithm we learned in our algorithms course; but I believe the algorithm your professor is asking you to implement is the Shunting-yard algorithm (http://en.wikipedia.org/wiki/Shunting-yard_algorithm). Instead of creating a token class, just break your expression into a sequence of characters (exclude spaces). I'm 100% sure this is the algorithm you need to implement. Please let me know if you have any questions! – Devarsh Desai Oct 08 '14 at 16:31
0

You are asked to implement an expression analyzer.

Here is a summary of how it is usually done. You scan the string from left to right, using the following procedures alternately. Each method consumes some of the text and returns an integer value.

  • A method to evaluate an integer: It starts with a digit. Collect all the contiguous digits and convert that to a value.
  • A method to evaluate a factor: If it starts with a digit, evaluate an integer. If it starts with a '(', evaluate an expression. If not, it is an error.
  • A method to evaluate a term: Evaluate a factor. While the next character is a * or a /, skip it, evaluate an additional factor, and multiply or divide the previous value by the new value.
  • A method to evaluate a sum: Evaluate a term. While the next character is a + or a -, skip it, evaluate an additional term and add or subtract the new value to the previous value.
  • A method to evaluate an expression: It starts with a '('. Skip it and evaluate a sum. If the next character is a ')', skip it. If not, it is an error.
Florian F
  • 1,300
  • 1
  • 12
  • 28
0

For simple String operations, like "5-2*10", one solution is:

import javax.script.ScriptEngineManager;
import javax.script.ScriptEngine;
import javax.script.ScriptException;

I don't want to consider the idea of not importing.

Basically, this is the code for the "Calculate" button, assuming that the expression 5-2*10 was introduced in a TextField:

ScriptEngineManager mgr = new ScriptEngineManager();
        ScriptEngine engine = mgr.getEngineByName("JavaScript");
        String r = jTextField1.getText();
        try {
            jTextField1.setText(engine.eval(r).toString());

        } catch (ScriptException ex) {
            Logger.getLogger(MegaCal.class.getName()).log(Level.SEVERE, null, ex);
        }
Insanovation
  • 337
  • 6
  • 21