stack

import java.util.*;
import java.io.*;

class Token
{
int tipe,value;

static final int END = 0;
static final int OP= 1;
static final int KURUNG_BUKA = 2;
static final int KURUNG_TUTUP= 3;
static final int CONST = 4;
static final int UMINUS = 5;
static final int ERROR = 6;

static final int MINUS = 7;
static final int PLUS = 8;
static final int DIV = 9;
static final int MUL = 10;


Token(int tipe, int value)
{
this.tipe=tipe;
this.value = value;
}
}

class SimpleParser
{
String data;
Stack stackValue = new Stack();
Stack stackState = new Stack();
int pos = 0;
int[][] action = new int[11][6];
int[] next = new int[11];
int[] reduction = new int[11];
int[] prec = new int[100];
boolean[] needToken = new boolean[11];
static final int REDUCTION = 100;
static final int SHIFT_REDUCTION = 101;
static final int ERROR = 102;
static final int SUKSES = 103;


SimpleParser(String data)
{
this.data = data + ";";
this.pos = 0;
for (int i=0;i<=10;i++)
{
next[i] = 0;
needToken[i] = true;
reduction[i] = 0;
}
next[1] = 2;
next[3] = 7;
next[5] = 8;
next[6] = 9;

needToken[4] = false;
needToken[8] = false;
needToken[10] = false;

reduction[4] = 1;
reduction[8] = 2;
reduction[9] = 3;
reduction[10] = 3;

prec[Token.MINUS] = 1;
prec[Token.PLUS] = 1;
prec[Token.DIV] = 2;
prec[Token.MUL] = 2;

// S -> .E
action[1][Token.END] = ERROR ;
action[1][Token.KURUNG_BUKA] = 3;
action[1][Token.KURUNG_TUTUP] = ERROR;
action[1][Token.CONST] = 4;
action[1][Token.OP] = ERROR;
action[1][Token.UMINUS] = 5;

// S -> E.
// E -> E. op E
action[2][Token.END] = SUKSES ;
action[2][Token.KURUNG_BUKA] = ERROR;
action[2][Token.KURUNG_TUTUP] = ERROR;
action[2][Token.CONST] = ERROR;
action[2][Token.OP] = 6;
action[2][Token.UMINUS] = ERROR;

// E -> (.E)
action[3][Token.END] = ERROR ;
action[3][Token.KURUNG_BUKA] = 3;
action[3][Token.KURUNG_TUTUP] = ERROR;
action[3][Token.CONST] = 4;
action[3][Token.OP] = ERROR;
action[3][Token.UMINUS] = 5;

// E -> CONST.
action[4][Token.END] = REDUCTION ;
action[4][Token.KURUNG_BUKA] = REDUCTION;
action[4][Token.KURUNG_TUTUP] = REDUCTION;
action[4][Token.CONST] = REDUCTION;
action[4][Token.OP] = REDUCTION;
action[4][Token.UMINUS] = REDUCTION;

// E -> UMINUS . E
action[5][Token.END] = ERROR ;
action[5][Token.KURUNG_BUKA] = 3;
action[5][Token.KURUNG_TUTUP] = ERROR;
action[5][Token.CONST] = 4;
action[5][Token.OP] = ERROR;
action[5][Token.UMINUS] = 5;

// E -> E op . E
action[6][Token.END] = ERROR ;
action[6][Token.KURUNG_BUKA] = 3;
action[6][Token.KURUNG_TUTUP] = ERROR;
action[6][Token.CONST] = 4;
action[6][Token.OP] = ERROR;
action[6][Token.UMINUS] = 5;

// E -> (E.)
// E -> E. op E
action[7][Token.END] = ERROR ;
action[7][Token.KURUNG_BUKA] = ERROR;
action[7][Token.KURUNG_TUTUP] = 10;
action[7][Token.CONST] = ERROR;
action[7][Token.OP] = 6;
action[7][Token.UMINUS] = ERROR;

// E -> UMINUS E.
// E -> E .op E
action[8][Token.END] = REDUCTION ;
action[8][Token.KURUNG_BUKA] = REDUCTION;
action[8][Token.KURUNG_TUTUP] = REDUCTION;
action[8][Token.CONST] = REDUCTION;
action[8][Token.OP] = REDUCTION;
action[8][Token.UMINUS] = REDUCTION;

// E -> E op E.
// E -> E .op E
action[9][Token.END] = REDUCTION;
action[9][Token.KURUNG_BUKA] = REDUCTION;
action[9][Token.KURUNG_TUTUP] = REDUCTION;
action[9][Token.CONST] = REDUCTION;
action[9][Token.OP] = SHIFT_REDUCTION;
action[9][Token.UMINUS] = REDUCTION;

// E -> (E).
action[10][Token.END] = REDUCTION ;
action[10][Token.KURUNG_BUKA] = REDUCTION;
action[10][Token.KURUNG_TUTUP] = REDUCTION;
action[10][Token.CONST] = REDUCTION;
action[10][Token.OP] = REDUCTION;
action[10][Token.UMINUS] = REDUCTION;



}

Token getToken(int istate)
{
int state=1;
String buf = "";
while(true)
{
char c = data.charAt(pos++);
if (state==1)
{
while(Character.isSpace(c))
{
c = data.charAt(pos++);
}
if (c=='+')
return new Token(Token.OP,Token.PLUS);
else if (c=='-')
{
if (istate==2 || istate==7 ||
istate==8 || istate==9)
return new Token(Token.OP,Token.MINUS);
else
return new Token(Token.UMINUS,0);
}
else if (c=='*')
return new Token(Token.OP,Token.MUL);
else if (c=='/')
return new Token(Token.OP,Token.DIV);
else if (c=='(')
return new Token(Token.KURUNG_BUKA,0);
else if (c==')')
return new Token(Token.KURUNG_TUTUP,0);
else if (c==';')
return new Token(Token.END,0);
else if (Character.isDigit(c))
{
state=2;
pos--;
}
else
return new Token(Token.ERROR,0);
}
else if (state==2)
{
if(Character.isDigit(c))
{
buf += c;
}
else
{
pos--;
return new Token(Token.CONST,Integer.parseInt(buf));
}
}
}
}

void reduc(int state)
{
rule(state);
int red = reduction[state];
for(int i = 0;i stackState.pop();
int istate = ((Integer)(stackState.peek())).intValue();
istate = next[istate];
stackState.push(new Integer(istate));
}

void rule(int state)
{
if (state==4)
{
}
else if (state==8)
{
int val1 = ((Token)(stackValue.pop())).value;
stackValue.pop();
int res = -val1;
stackValue.push(new Token(Token.CONST,res));
}
else if (state==9)
{
int val2 = ((Token)(stackValue.pop())).value;
int op = ((Token)(stackValue.pop())).value;
int val1 = ((Token)(stackValue.pop())).value;
int res = 0;
if(op==Token.PLUS)
res = val1 + val2;
else if (op==Token.MINUS)
res = val1 - val2;
else if (op==Token.MUL)
res = val1 * val2;
else if (op==Token.DIV)
res = val1 / val2;
stackValue.push(new Token(Token.CONST,res));
}
else if (state==10)
{
stackValue.pop();
int val1 = ((Token)(stackValue.pop())).value;
stackValue.pop();
stackValue.push(new Token(Token.CONST,val1));
}
}

void resolve(Token token, int state)
{

Token token1 = (Token)(stackValue.pop());
Token token2 = (Token)(stackValue.pop());
int tokenPrec = prec[token.value];
int rulePrec = prec[token2.value];
stackValue.push(token2);
stackValue.push(token1);
if (rulePrec >=tokenPrec)
{
reduc(state);
}
else
{
stackValue.push(token);
stackState.push(new Integer(6));
tokenValid = false;
}
}


boolean tokenValid = false;

Token parse()
{
int state = 1;
int a;
Token token = null;
stackState.push(new Integer(1));
while(true)
{
state = ((Integer)(stackState.peek())).intValue();
//System.out.println("State " + state);
if (needToken[state])
{
if (!tokenValid)
{
token = getToken(state);
tokenValid = true;
}

if(token.tipe==Token.ERROR)
return token;
a = action[state][token.tipe];
if (a == REDUCTION)
reduc(state);
else if (a==SHIFT_REDUCTION)
resolve(token,state);
else if(a==ERROR)
return new Token(Token.ERROR,0);
else if(a==SUKSES)
return (Token)(stackValue.pop());
else
{
stackValue.push(token);
stackState.push(new Integer(a));
tokenValid = false;
}
}
else
{
reduc(state);
}
}
}

}

public class Parser
{
public static void main(String[] args)
{
String data = "100 * 4 - -(1* 2) + -5 + -5";
SimpleParser sp = new SimpleParser(data);
System.out.println(data);
Token t = sp.parse();
if (t.tipe == Token.ERROR)
System.out.println("SYNTAK ERROR");
System.out.println(t.value + "");
DataInputStream in = new DataInputStream(System.in);
try
{
in.readLine();
}
catch(Exception ex)
{
}
}
}