« November 2003 | Main | January 2004 »
vakar prausdamasis pastebėjau, kad nuo rankos atsirišo raištelis, kurį studentė ieva atveržė dovanų iš kinijos. "chm, ženklas" pagalvojau ir padėjau raištelį į šalį. po to besišluostydamas atsegiau ir vos neišnėriau auskaro iš antakio, įsisegiau atgal tylomis. px tie ženklai ;)
č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) ;
}
eidamas pro lukiškių kalėjimą pastebėjau vaikų koloną sustatytą po du. koloną rokavo mėlyna uniforma vilkintis prižiūrėtojas.
šivis sakė, kad jį vaikystėj į šokolado fabriką vesadvo, mane tai px, bent jau į kuro aparatūros arba grigiškių popieriaus gamyklą, bet dabar pasirodo viskas blogiau - dabar vaikus į ekskursiją į lukiškes vedžioja :)
važiuojant tuo autobusu aš mačiau daug nuostabių dalykų.
vienas nuostabus dalykas buvo girtos žvingaliojančios studentės, kurios iš pradžių į mane pasižiūrėjo, po to nusišypsojo, po to prunkštė į saują ir galų gale paklausė, ar šis autobusas važiuoja į justiniškes. jsutiniškėse joms reikėjo karolinos klubo.
kitas nuostabus dalykas buvo du paaugliai. paaugliškai dizzzy nuo paaugliško alkoholio ir paaugliška greitakalbe bėrė ir kūrė planus. galų gale iššoko iš autobuso vienoje stotelėje ir užtagino stotelės ženklą markeriais. atgal grįžo pilnom kelnėm adrenalino "ten biškį į galą apsilažalinau" "px tai taip ir turėjo būt" ir jau įsivaizdavo, kaip lyg niekur nieko pro tą vietą eis su draugais ir klasiokais ir kaip vat jie pamatys jų tagus ir vat kaip bus vat. dar jie kūrė planus apie tai, kaip būtų geras, kai atidaro tėvai duris, o tu įriedi kūlversčiais namo, bet čia reikia daryt tiktai, kai esi visai blaivus, nes jeigu "biškį ant ribos", tai geriau nereikia rizikuot, gali parišt
20:39
20:57 autobusas veža namo
20:45 pradėt ruoštis
pablogint per 6 minutes
po gero koncerto šokau ant karštų peilių ir mažai miegojau. įeina ve ir sako "einam parūkyt" vat ir pabloginau per 6 minutes
masačiusetsas
