/** Name: tdparse
    Description: parser class for tdparse project
    Programmer: Spencer R. Shimko
    Date: 03-25-2003
**/

import java.util.*;

public class parser{
	static LinkedList results = new LinkedList(); // holds results to be returned

	static Hashtable s_vars = new Hashtable(); // hashtable to store .see vars

	/** parse: performs parsing
	    receives: LL of input line
	    returns: LL of output lines (error or interperted output lines)
	**/
	public static LinkedList parse(LinkedList input){
		String line; // will hold input line while parsing
		String[] p_line; // line after parsing
		String[] t_line; // temp line

		//begin parsing input line by line
		for (int x=0; x<input.size();x++){
			line =(String) input.get(x); // retreive line from L.L. input
			/* gradernote: I'm still not sure why but when using regex
			split in java the first element in the returned array appears
			to be empty unless the regex is unmatched... this is how I will
			know if the text was found in later conditional statements */
			System.out.println(line);
			// split the input to see if it is a print statement
			p_line=line.split("^\\s*[P|p][R|r][I|i][N|n][T|t]\\s+",2);

			// if the input is a print statement
			if (p_line.length==2){
////////////////////////////////PRINT STATEMENT
				Float eval_expr;
				eval_expr=parseExpr(p_line[1]);
				if ( eval_expr == null){
					results.add("Error: Line "+(x+1)+" PRINT expression appears to be invalid!");
				} else // the var. name and expression are valid...place in hashtable
					results.add("Output: Line "+(x+1)+ ": " + eval_expr);
////////////////////////////////END PRINT STATEMENT
			} // end if print statement
			else { // else not print statement
				// check the input to see if it is a let statement
				p_line=line.split("^\\s*[L|l][E|e][T|t]\\s+",2);

			    // if the input is a let statement
			    if (p_line.length==2){
////////////////////////////////LET STATEMENT
					// start by getting the variable name and the expression split
					p_line=p_line[1].split("\\s*=\\s*");

					// ensure that the varible name starts with a valid alpha char and isnt blank
					if ((!p_line[0].equals(""))&&(isChar(p_line[0].charAt(0)))){
						// we have a valid variable name so verify and evaluate the expression
						t_line=p_line[0].trim().split("[^0-9A-Za-z]");
						if (t_line.length==1){
							Float eval_expr;
							eval_expr=parseExpr(p_line[1]);

							if ( eval_expr == null){
								results.add("Error: Line "+(x+1)+" expression appears to be invalid!");
							} else{ // the var. name and expression are valid...place in hashtable
						    	s_vars.put(p_line[0],eval_expr.toString());
							}
						}// end if variable name valid
						else { // varible name contains non-alpha/numeric chars
							results.add("Error: Line "+(x+1)+" variable name appears to be invalid!");
						}
					} else { //invalid varible name
						results.add("Error: Line "+(x+1)+" variable name appears to be invalid!");
					}
///////////////////////////////END LET STATEMENT
				}// end if let statement
				else if(!(line.length()<2)) // else not a blank line we have an error
				{ // input error
					results.add("Error: Line "+(x+1)+" does not appear to be a print or let statement");

				}
			} // end else not print statement
		}// end for loop until EOF
		return results;
	} // end method parse

	/** parseExpr: parse expression gramatically
	    receives: String expression to be parsed
	    returns: value of expression or null if expression is invalid
	**/
	private static Float parseExpr(String ex){
		String[] e_line; // array of parsed expressions
		String[] t_line; // stores temporary parsing (lookahead guesses)
		Float temp; // stores returned values temporarily for null checking

		// perform parsing according to order of operations
		e_line=ex.split("\\s*\\(\\s*"); // split String based on parentheses

		if (e_line.length>1){// to save alot of cycles if there aren't paren... ignore this
			for (int y=0;y<e_line.length;y++){

				// this do loop takes care of ")" and the effect they have on the string
				do{
					t_line=e_line[y].split("\\s*)\\s*",2); // lookahead for closing paren
					if (t_line.length>1){ // if expression conatins ")"
						// we can now evaluate part of the expression b/c we have ")"
						temp=parseTerm(t_line[0]);
						// null check
						if (temp!=null){
							e_line[y]=temp.toString().concat(t_line[1]);
						}else { return null;}
					}
				} while (t_line.length != 1); // do until there are no more ")" in this expression
			} // end for loop finding ")" and evaluating

			// the parentheses have been accounted for and removed...
			// the string can now be put back together again
			// When putting the string back together we must keep in mind
			// that the first element in the array was not inside a parentheses
			// so we do that one last
			for (int y=(e_line.length-1);y>=1;y--)
				e_line[y-1].concat(e_line[y]);
			temp=parseTerm(e_line[1]);
			if (temp!=null){
				ex=e_line[0].concat(temp.toString());
			}else {return null;}
		}// end if paren found

		return parseTerm(ex);
	}// end method parseExpr

	/** parseTerm: prase arithmetic expression without parentheses
	    receives: input string
	    returns: Float value or null if invalid expression
	**/
	private static Float parseTerm(String t){
		String[] p_line; // same as above... stores line at various states of parsing
		String[] t_line; // same as above... stores line at various states of parsing
		String signs=""; //store order of signs to be done

		// now we should just have variable names or values in p_line
		// so to avoid unnecessary cycles again check these for validity
		// here we split on any sign
		p_line=t.split("\\s*[+\\-*/]\\s*");
		for(int x=0;x<p_line.length;x++){
			// lets see if its a number (int or float) or a variable name
			if (isChar(p_line[x].charAt(0))&&(!s_vars.containsKey(p_line[x]))){
				results.add("Error: "+ p_line[x] + " not a valid delcared varible!");
				return null;
			} else if (!isChar(p_line[x].charAt(0))){ // else if it starts with a digit
				// lets make sure it's a valid numeric expression
				t_line=p_line[x].split("\\.");
				if (t_line.length>2){// if there are too many decimals
					results.add("Error: "+ p_line[x] + " too many decimals!");
				    return null;
				}
				t_line=p_line[x].split("[^0-9\\.]"); // parse number to see if it has nonnumeric
				if (t_line.length>1){ // if the numeric expression contains non-numeric/decimal
					results.add("Error: "+ p_line[x] + " numeric expression contains weird character!");
				    return null;
				}

			} else { // the variable name was found... replace with declared value
				// swaps varible's name for the actually value
				t=t.replaceFirst(p_line[x],(String)s_vars.get(p_line[x]));
				p_line[x]=(String)s_vars.get(p_line[x]);
			}
		}// end for looping through possible terms

		// compress numeric terms into smaller array for easier indexing
		int temp=0;
		t_line=p_line;
		for (int y=0;y<p_line.length;y++)
			if (p_line[y].length()>0){ // if it is a valid number
				t_line[temp]=p_line[y];
				temp++;
			}
		p_line=t_line; // the p_line will store a very concise array of numeric expressions


		///////////////// by this point all strings in p_line are valid numeric expressions
		///////////////// lets do some arithmetic but we have to go back to the original
		///////////////// string t to get the symbols
		if ((t.charAt(0)=='-')||(isChar(t.charAt(0)))||(isNum(t.charAt(0)))){ // if the first char is a unary minus
			t_line=t.split("[0-9\\.]");
			for (int z=0; z<t_line.length; z++){
				if (t_line[z].length()==1){// add the operator to the LL if it's not an empty string
					signs=signs.concat(t_line[z]);
				} else if ((t_line[z].length()==2) && (t_line[z].charAt(1)=='-')){
					// negative number found... add operator to stack
					signs=signs.concat(String.valueOf(t_line[z].charAt(0))); // add the sign to the list
					// now account for the unary minus
					p_line[z]=String.valueOf("-").concat(p_line[z]);
				} else if (t_line[z].length()>1){ // incorrect number format
					results.add("Error: "+ t_line[z] + " not a valid term!");
			   		return null;
				}// end if trying to match unary minus
			} // end for loop retreieving operators
			if (t.charAt(0)=='-')
				p_line[0]=String.valueOf("-").concat(p_line[0]);
		} // end if first digit is negative
		else {
		  	results.add("Error: incorrect numeric expression... start invalid!");
			return null;
		}

		// now we need to loop through the operations doing div.and mult. first L->R
		while ((p_line.length>1)&&(signs.length()>1)) // used to restart for loop when arrays are resized
		for(int z=0; z<signs.length();z++){
			if (signs.charAt(z)=='*'){ // if this is multiplication
				p_line[z]=Float.toString(Float.parseFloat(p_line[z])*Float.parseFloat(p_line[z+1]));
				//now to compress the lists and start over
				signs=signs.replaceFirst("[*]","");
				for (int x=z; x<(signs.length()-1);x++){
					p_line[x+1]=p_line[x+2]; // compresses array b/c one term has been removed
				}
				break;
			} else if (signs.charAt(z)=='/'){ // if this is division
				p_line[z]=Float.toString(Float.parseFloat(p_line[z])/Float.parseFloat(p_line[z+1]));
				//now to compress the lists and start over
				signs=signs.replaceFirst("[/]","");
				for (int x=z; x<(signs.length()-1);x++)
					p_line[x+1]=p_line[x+2]; // compresses array b/c one term has been removed
			break;
			} // end else '/'
		} // end for loop checking for * / from L->R


		while ((p_line.length>1)&&(signs.length()>1))// used to restart for loop when arrays are resize
		for(int z=0; z<signs.length();z++){
			if (signs.charAt(z)=='+'){ // if this is addition
				p_line[z]=Float.toString(Float.parseFloat(p_line[z])+Float.parseFloat(p_line[z+1]));
				//now to compress the lists and start over
				signs=signs.replaceFirst("[+]","");
				for (int x=z; x<(signs.length()-1);x++)
					p_line[x+1]=p_line[x+2]; // compresses array b/c one term has been removed
				break;
			} else if (signs.charAt(z)=='-'){ // if this is subtraction
				p_line[z]=Float.toString(Float.parseFloat(p_line[z])-Float.parseFloat(p_line[z+1]));
				//now to compress the lists and start over
				signs=signs.replaceFirst("[\\-]","");
				for (int x=z; x<(signs.length()-1);x++)
					p_line[x+1]=p_line[x+2]; // compresses array b/c one term has been removed
				break;
			} // end else '/'
		} // end for loop checking for + - from L->R
		return (Float.valueOf(p_line[0])); // p_line[0] will contain the eval. expression


	}// end parseTerm method

	/** isChar: is the parameter an alpha character?
	    receives: character
	    returns: true if the parameter is a alpha char, false otherwise
	**/
	private static boolean isChar(char x){
		for (int y='a';y<='z';y++)
			if (x==y) return true;
		for (int y='A';y<='Z';y++)
			if (x==y) return true;
		return false;
	} // end method isChar

	/** isNum: is the parameter a numeric
	    receives: character
	    returns: true if the parameter is numeric
	**/
		private static boolean isNum(char x){
			for (int y='0';y<='9';y++)
				if (x==y) return true;
			return false;
	} // end method isNum
}// end class parser