« požiūris | Pirmas | laukiam kalėdų »

infix to postfix

čia prireikė staiga pasikonvertuoti loginius reiškinius į postfiksinę formą
a or b and c ---> abc and or

ve su margo jau kažkada rašė klasę, skirtą generuoti SQLą pagal paieškos laukelyje suvestus žodžius tipo "ožys AND karvė OR telyčia", bet bėda ta, kad jų rašyta klasė iškart ir sprendė reiškinį (t.y generavo SQL), o man reikėjo grynos transformacijos, kad po to galėčiau reiškinį įrašyt į duombazę kažkokiu jobnutu formatu, tai rytą praleidau palinkęs virš popieriaus lapelio, o po to nutariau prasigooglint:

labiausiai jobnutas algoritmo aprašymas ever - click
padorus aprašymas, bet neimant domėn skliaustelių - click
ačiū Jah, dar yra pasaulyje žmonių su matematiniu išsilavinimu - click

go for code kaipsakant...


import java.util.EmptyStackException;
import java.util.Iterator;
import java.util.Stack;
import java.util.Vector;

/**
* @author mic
* mic@hardcore.lt; http://blog.hardcore.lt/mic
*/
public class InfixToPostfix {
public static Vector convert(Vector infix){
Vector postfix = new Vector() ;
Stack operatorStack = new Stack() ;
while(!infix.isEmpty()){
Lexem i = (Lexem) infix.remove(0) ;

if(i.isOperand()) {
postfix.add(i);
} else if(i.isOperator()) {
boolean pushed = false ;
while(!pushed){
if(operatorStack.empty()){
operatorStack.push(i) ;
pushed = true ;
} else {
Lexem stackTop = null ;
try{
stackTop = (Lexem) operatorStack.peek() ;
} catch (EmptyStackException e) {
return null ;
}
int action = stackTop.decideAction(i) ;

if(Lexem.ACTION_PUSH == action) {
operatorStack.push(i) ;
pushed = true ;
} else if(Lexem.ACTION_POP == action) {
postfix.add(operatorStack.pop()) ;
} else if(Lexem.ACTION_ERROR == action){
return null ;
} else if(Lexem.ACTION_NONE == action){
operatorStack.pop() ;
pushed = true ;
}
}
}
}
}
while(!operatorStack.empty()) {
postfix.add(operatorStack.pop()) ;
}
return postfix ;
}

public static void main(String argv[]){
Vector v = new Vector() ;
v.add(new BoolLexem("a")) ;
v.add(new BoolLexem("OR")) ;
v.add(new BoolLexem("b")) ;
v.add(new BoolLexem("AND")) ;
v.add(new BoolLexem("c")) ;

System.out.println("Converting expression: ") ;
for(Iterator i = v.iterator(); i.hasNext() ;)
System.out.print(((BoolLexem)i.next()).toString() + " ") ;
System.out.println("") ;

v = InfixToPostfix.convert(v) ;

System.out.println("Result: ") ;
for(Iterator i = v.iterator(); i.hasNext() ;)
System.out.print(((BoolLexem)i.next()).toString() + " ") ;
System.out.println("") ;
}
}
class BoolLexem implements Lexem {
String lexem ;
public BoolLexem(String s) {
lexem = s ;
}

public boolean isOperator() {
return lexem.equals("AND") || lexem.equals("OR") || lexem.equals("(") || lexem.equals(")") ;
}

public boolean isOperand() {
return !isOperator() ;
}

public int decideAction(Lexem ll) {
BoolLexem l = (BoolLexem) ll ;
if(l.equals("("))
return ACTION_PUSH ;

if(lexem.equals("AND")) {
if(l.equals("AND"))
return ACTION_POP ;
if(l.equals(")"))
return ACTION_POP ;
if(l.equals("OR"))
return ACTION_POP ;
} else if(lexem.equals("OR")){
if(l.equals("AND"))
return ACTION_PUSH ;
if(l.equals(")"))
return ACTION_POP ;
if(l.equals("OR"))
return ACTION_POP ;
} else if(lexem.equals("(")){
if(l.equals("AND"))
return ACTION_PUSH ;
if(l.equals(")"))
return ACTION_NONE ;
if(l.equals("OR"))
return ACTION_PUSH ;
}
return ACTION_ERROR ;
}

public String toString(){
return lexem ;
}

public boolean equals(String s) {
return lexem.equals(s) ;
}
}


/**
* @author mic
* mic@hardcore.lt; http://blog.hardcore.lt/mic
*/
public interface Lexem {
public static final int ACTION_ERROR = -1 ;
public static final int ACTION_NONE = 0 ;
public static final int ACTION_POP = 1 ;
public static final int ACTION_PUSH = 2 ;

public boolean isOperator() ;
public boolean isOperand() ;
public int decideAction(Lexem l) ;
}


Komentarai

O tikrai
(a or b) and c ---> abc and or ??
man kažkaip neša labiau, kad
(a or b) and c ---> ab or c and
arba
(a or b) and c ---> cab or and

a jo, tiksliai, turėjo būt

a or b and c --> abc and or