// Online calculator with expression trees and shift-reduce parser

#![allow(dead_code)]
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(unused_parens)]
#![allow(non_camel_case_types)]
use crate::Expr::*;    
//use std::rc::Rc;
use std::fmt::{Display,Formatter,Result};
// online calculator in Rust, with shift-reduce parser

///// expression trees
#[derive(Clone)]
enum Expr
{
   Val(i32),
   Plus(Box<Expr>,Box<Expr>),  // recursion requires smart pointer
   Times(Box<Expr>,Box<Expr>), 
   Neg(Box<Expr>),
   Sym(char),
   EOF,
   Dummy,
}  // no copy/clone trait defined


fn eval(e:&Expr) -> i32
{
   match e {
     Val(x) => *x,  // x is a ref because e is
     Plus(bx,by) => eval(bx) + eval(by), // deref coercion works nicely here
     Times(x,y) => eval(x) * eval(y),
     Neg(x) => -1 * eval(x),
     _ => panic!("Expression can't be evaled"),
   }//match
}//eval

impl Display for Expr
{
    fn fmt(&self, f: &mut Formatter<'_>) -> Result  // required by trait
    {
       match self {
         Val(x) => write!(f,"{}",x),
	 Plus(x,y) => write!(f,"({}+{})",x,y),
	 Times(x,y) => write!(f,"{}*{}",x,y),
	 Neg(x) => {if let Neg(y)=&**x {write!(f,"{}",y)} else
	               {write!(f,"-{}",x)}},
	 /*Neg(x) => write!(f,"-{}",x),*/
	 Sym(s) => write!(f," {} ",s),
	 EOF => write!(f," EOF "),
	 Dummy => write!(f," Dummy "),
       }//match
    }
}// impl Display for Expr


/// Tokenizer later

/// operator precedence parser
fn precedence(e:&Expr)->u32
{
   match e {
      Val(_) => 250,
      Sym('+') => 100,
      Sym('*') => 200,
      Sym('-') => 220,
      Sym('(') => 500,
      Sym(')') => 10,
      EOF => 5,
      _ => 0,
   }
}
fn prec(a:&Expr, b:&Expr) -> bool
{
  precedence(a) <= precedence(b)
}
// assume universal left-associativity.

fn ateof(e:&Expr) -> bool
{ match e { 
    EOF => true,
    _ => false, 
  }
}
    
  

fn parse(tokens:&Vec<Expr>) -> Expr
{ 
  let mut stack:Vec<Expr> = Vec::new();
  // look at up to 3 symbols at a time
  let mut ti:usize = 0; // indexes tokens
  let mut lookahead = &tokens[ti];
  while !(ateof(lookahead) && stack.len()==1)
  {
     let (mut a,mut b,mut c) = (&Dummy,&Dummy,&Dummy);
     let sl = stack.len();
     if sl>0 {c=& stack[sl-1];}
     if sl>1 {b=& stack[sl-2];}
     if sl>2 {a=& stack[sl-3];}
     match (a,b,c) {
       (Sym('('),e,Sym(')')) if prec(lookahead,a) => {
           stack.remove(sl-3);
	   stack.pop();
       },
       (e1,Sym('+'),e2) if prec(lookahead,b) => {
           let e = Plus(Box::new(e1.clone()),Box::new(e2.clone()));
           stack.truncate(sl-3);
	   stack.push(e); // e moved to stack, owned by stack?
       },
       (e1,Sym('*'),e2) if prec(lookahead,b) => {
           let e = Times(Box::new(e1.clone()),Box::new(e2.clone()));
           stack.truncate(sl-3);
	   stack.push(e); // e moved to stack, owned by stack?
       },
       (_,Sym('-'),e1) if prec(lookahead,b) => {
           let e = Neg(Box::new(e1.clone()));
           stack.truncate(sl-2);
	   stack.push(e); // e moved to stack, owned by stack?
       },
       (_,_,_) if ti<tokens.len()-1 => {  // shift
           stack.push(lookahead.clone());
	   ti += 1;
           lookahead = &tokens[ti];
       },
	_ => {
           for ex in stack { print!("{}::",ex);}
	   println!();
   	   panic!("parse error")
       }
     } // match
  }// while
  return stack.pop().unwrap();
}//parse

fn main()
{
   let test:Vec<Expr>=vec![Val(3),Sym('+'),Val(5),Sym('*'),Sym('-'),Val(2),EOF];
   let exp = parse(&test);
   println!("{} = {}",exp,eval(&exp));
   let test2:Vec<Expr>=vec![Sym('-'),Sym('('),Val(3),Sym('+'),Val(5),Sym(')'),Sym('*'),Val(2),EOF];
   let exp2 = parse(&test2);
   println!("{} = {}",exp2,eval(&exp2));

}//main