operator precedence using list in java

Question

Possible Duplicate:
Evaluating a math expression given in string form

i need some help in our assignment. im trying to create a program that will compute using operator precedence. if it is possible, i want to compute the expression inside an arraylist. for ex. [4+2x2-3] should calculate 2x2 first so the result will be [4+4-3] and so on... my program only calculates the first operation but couldn't reiterate through others. also.. it only calculates when the highest priority operator is in the beginning. ex. [2^1-2] becomes [2-2]. but when [2-1^2] it doesn't do anything.thanks for help

List<String> subroutine = new CopyOnWriteArrayList<String>(input);
        for(String i : subroutine)
    {
        switch(currentstate)
        {
            case q0:
                if(isDigit(i))
                {
                    currentstate = q1;
                }
            break;

            case q1:
                if(i.equals("^"))
                {
                    maxPriority = i;
                    int index = subroutine.indexOf(maxPriority);
                    int num1 = Integer.parseInt(subroutine.get(index-1));
                    int num2 = Integer.parseInt(subroutine.get(index+1));
                    int total = (int) Math.pow(num1, num2);

                    String stringTotal = Integer.toString(total);
                    String addToExp = subroutine.set(index, stringTotal);
                    int indexAddToExp = subroutine.indexOf(stringTotal);
                    subroutine.remove(indexAddToExp+1);
                    subroutine.remove(indexAddToExp-1);
                    System.out.println(subroutine);
                }
                else if( (i.equals("x") || i.equals("/")) && (!input.contains("^")) )
                {
                    if(i.equals("x"))
                    {
                        maxPriority = i;
                        int index = subroutine.indexOf(maxPriority);
                        int num1 = Integer.parseInt(subroutine.get(index-1));
                        int num2 = Integer.parseInt(subroutine.get(index+1));
                        int total = num1 * num2;

                        String stringTotal = Integer.toString(total);
                        String addToExp = subroutine.set(index, stringTotal);
                        int indexAddToExp = subroutine.indexOf(stringTotal);
                        subroutine.remove(indexAddToExp+1);
                        subroutine.remove(indexAddToExp-1);
                    }

You can't do this without a stack. Google for 'shunting-yard algorithm' for one way to do it. — user207421, Oct 12 '12 at 12:35
i've already made a program using shunting yard algorithm postfix. but im confused with this infix notation. — Tokuchi Toua, Oct 12 '12 at 12:53
Infix notation is what you already have. What's to be confused about? — user207421, Oct 13 '12 at 07:49

score 4 · Answer 1 · edited May 23 '17 at 11:56

4

You should consider building up a more complex structure of expressions than simply using a Collection of strings.

Basically you will want to parse the given arithmetic expression into an abstract syntax tree based on a given context free grammar, which could roughly look like this:

ArithmethicExpression := CompoundExpression | LiteralExpresion
LiteralExpression := {0-9}+ (meaning at least one digit)
CompoundExpression := LiteralExpression FunctionExpression LiteralExpression

This grammar is just a rough idea of what you need, but certainly it will help you to make it easier for you to implement what you need.

There's another question here, which is clearly related. Especially this answer is really interesting for you.

edited May 23 '17 at 11:56

Community

1
1

answered Oct 12 '12 at 12:11

Markus

2,071
4
22
44

im sorry but, i dont really understand it. lol – Tokuchi Toua Oct 12 '12 at 12:32
A regular grammar won't do it. He needs a context-free grammar to handle precedence. – user207421 Oct 12 '12 at 12:36
@EJP I think you are right. At least hinting to some formal grammar is helpful. I will edit the answer. – Markus Oct 12 '12 at 12:39

operator precedence using list in java

1 Answers1