package trees.expressiontrees;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;
import java.util.Iterator;

public class Helper {
	char lookahead;
	Scanner sc;
	String input;
	int ind = 0;
	
	Helper() {
		sc = new Scanner(System.in);
		System.out.print("Enter an expression ending with $: ");
		input = sc.nextLine();
	}
	
	/* This method extracts the tokens from input stream
	 * and puts them in a queue.
	 */ 
	Queue<Token> lexer() throws Exception {
		ArrayDeque<Token> result = new ArrayDeque<Token>();  // the result vector
		int val = 0;
		lookahead = getC();
		do {  // reads tokens from input
			if (Character.isDigit(lookahead)){ // reads token - number
				val = lookahead-'0';
				while (Character.isDigit(lookahead = getC()))
					val = val*10+lookahead-'0';
				result.add(new Operand(val)); // ads number to vector
			}
			else {  // reads token - opeads op to vector 
				switch(lookahead) {
					case '(': result.add(Operation.L_BRACE); break;
					case '+': result.add(Operation.PLUS); break;
					case '-': result.add(Operation.MINUS); break;
					case '*': result.add(Operation.MULT); break;
					case '/': result.add(Operation.DIV); break;
					case ')': result.add(Operation.R_BRACE); break;
					default: throw new Exception("Lexer: Error in expression"); 
				}		
				lookahead = getC();
			}
		} while (lookahead != '$');
		return result;
	}
	
	char getC() {
	    try {
	    	while(Character.isWhitespace(input.charAt(ind++)));
	    	return input.charAt(ind-1);
	    }
	    catch (Exception e) {
	    	return '$';
	    }
	}
	
	/* This method converts the infix notation
	 * to postfix notation
	 */
	Vector<Token> convert(Queue<Token> queue) throws Exception {
		Vector<Token> result = new Vector<Token>();  // the result vector
		Stack<Operation> st = new Stack<Operation>();  // stack to hold operations
		int val;
		Token nextToken;
		Iterator<Token> it = queue.iterator();
		while(it.hasNext()) {   // reads tokens from input
			nextToken = it.next();
			if(nextToken instanceof Operand) // reads token - number
				result.add(nextToken); // add number to vector
			else { // reads token - operaton
				if(nextToken == Operation.L_BRACE)
					st.push((Operation)nextToken);
				else if(nextToken != Operation.R_BRACE) 
					insert((Operation)nextToken, st, result);
				else
					insertBrace(st, result);
			}
		}
		while(!st.isEmpty())  // after end of input, tokens from stack
			result.add(st.pop()); // are added to vector
		return result;
	}
	
	/* This method pushes to vector
	 * next operation read.
	 */
	static void insert(Operation t, Stack<Operation> st, Vector<Token> v) {
		Operation tt;
		while(!st.isEmpty()) {
			tt = st.peek();
			if(tt.priority() >= t.priority())
					v.add(st.pop());
			else break;
		}
		st.push(t);
	}
	
	/* This method operates when 
	 * reads right brace in input stream
	 */
	static void insertBrace(Stack<Operation> st, Vector<Token> v) {
		Operation tt;
		while(!st.isEmpty()) {
			tt = st.pop();
			if(tt != Operation.L_BRACE)
					v.add(tt);
			else 
				break;
		}
	}
}