Best way to store an operator precedence table

[aravind326]

Hi,

I am just trying to do some program on arithmetic expression parsing.
So i want to store my operator precedence table in the program somehow.

I could use a multidimensional array, but that would be inefficient i guess.
Another idea i have is to use a HashTable, where the keys will be integers spcifying the precedence order, and the value can be an array or better an arraylist which can have the elements with the same precedence.

But still this will involve a lot of looping around as the precedence value, is the key and not the value.

Does anyone have a better proposition on how to do this?

Thanks,
Aravind

[harinath_2007]

Just a thought. (Might be silly)

How about using Strings. Store it in a string so that the index will be the precedence order of that character.
Just retrieve the desired operator using its index value..

Lets say : my string is

String operators="+&%^()^%$";

just retrieve using the index .

char c=operators.charAt(1);

PS: This is just a radom thought.Dont know if this suits your problem.. Ignore if it doesn't.

[aravind326]

Thanks.

This is a possible solution, which i also had thought of in the begginning.

But since there are many operators that are in the same precedence level, I preferred to store it in a table manner, so that for elements with the same precedence, it returns the same value, and then check for left to right/right to left associativity if required.

And also i wanted to be able to expand this later to include other operators as well into this as well. Relational operators for instance.

String is a possible solution, but i was thinking storing them in a mor tabular format would make things more clearer.

[JamesCherrill]

1. You can't assess "efficiency" unless you have a reasonable list of the various ways in which the data needs to be accessed and a rough count of how often each of those will happen. Do you need to find the priority for a given operator? Do you need a list of alloperators with the same priority? How often? etc etc.
   Write down the method signatures for the complete set of accessors that you would need to access your data. That's (a) the requirements statement for the data structure and (b) the starting point for your implementation.

2. Discussions of efficiency in Java are almost always premature. The compiler and runtime are really good nowdays at optimising your code, and if you are using this data structure for processing stuff that you just read in from a file then it's the file i/o that swamps everything else. Unless you have some very good reason otherwize you should encapsulate all your data structures behind public accessor methods, then start with a data structure that is really obvious and clear as to its purpose and implementation. IF sometime later you determine there really is an efficiency problem you can change the data structure without changing the accessor methods and therefore without breaking anything else.

If you post the accessor signatures, and a quick note of which will be used the most, we can make sensible suggestions for an easy and clear way to implement them.

[aravind326]

I am trying to do some infix-postfix conversion/evaluation now. And am trying to develop it into a small sort of mathermatical compiler/interpreter.

I just want to be able to get the precedence level of a given operator so that i can compare the precedence level.

This is what i have now.
I am storing the operators in a HashTable : Hashtable<Integer, ArrayList<Character>>
Where the key is the precedence level and the Arraylist will have operators of that precedence.

And to get the precedence I have a method like this :

    public int getPrecedence(Character operator){
        int precedenceVal = 0;
        for(Integer key : this.keySet()) {
            if(this.get(key).contains(operator)){
                precedenceVal = key;
                break;
            }
        }
        return precedenceVal;
    }

[JamesCherrill]

How about an O.O. implementation? Create an Operator class. Give it apublic int getPrecedence() method. Using Characters for Operators is hardly Java thinking, and what about 2-character operators: >= etc?

[aravind326]

Yes, i do have it as a separate class. I am pasting my whole class code here.

package com.expressioneval;

import java.util.ArrayList;
import java.util.Hashtable;

public class PrecedenceTable extends Hashtable<Integer, ArrayList<Character>>{

    private static final long serialVersionUID = -2771838131800698310L;

    public PrecedenceTable() {
        ArrayList<Character> array = new ArrayList<Character>();
        array.add('(');
        array.add(')');
        this.put(1, array);
        array = new ArrayList<Character>();
        array.add('*');
        array.add('/');
        array.add('%');
        this.put(2, array);
        array = new ArrayList<Character>();
        array.add('+');
        array.add('-');
        this.put(3, array);
    }

    public int getPrecedence(Character operator){
        int precedenceVal = 0;
        for(Integer key : this.keySet()) {
            if(this.get(key).contains(operator)){
                precedenceVal = key;
                break;
            }
        }
        return precedenceVal;
    }

}

I understand that having operators as characters is a problem.
I am reading from a String, thats why i had gone with character.
What do you suggest i can use unstead.
I am having the same problem, when coming to the evaluation part.
How do i evaluate using the expression, other than having to use switch case or some condition like that.

[JamesCherrill]

Here's the kind of thing you would do in an O.O. design.

 class Operator {

   public Operator(String symbol, int precedence) ...
   // eg  new Operator(">=", 5);

   public String getSymbol() ... 
   public int getPrecedence() ...

   public List<Operator> getOpsWithSamePrecedence() ...

   public static Operator getOperator(String symbol) ... 
   // returns the Operator with that symbol, or null if symbol is not valid

   // could use subclasses to implement evaluate methods for each operator...
   public int evaluate(int arg1, int arg2) ...
   public boolean evaluate(boolean arg1, boolean arg2) ...
   ...

[aravind326]

Thanks.

That seems to be a good way.
Let me try that out.