#!/usr/bin/perl 
#use Memoize;
#DAMIAN KNOPP
#336  DATA STRUCTURES  T/TH 12:00-2:20
#Program to store in 2 polynomials and manipulate them with
#add,sub,mult,eval,erase,and write functions.
#I used an array to store the polynomials.
########################################################################


#######################################################################
#Accesses the nodes one at a time circularly
#######################################################################
sub Getnode(\@) {
#makes array circular and returns next node
my $listref = shift;
my $element = $listref -> [0];
push(@$listref,shift @$listref);
return $element;
}
#########################################################################
#Error message
###########################################################################
sub Errormsg{
print "INVALID POLYNOMIAL!\n";
print "USAGE:number of terms(n),e1,c1,e2,c2,...\n";
}
############################################################################
#To access the last 2 elements of poly, (one exp and one coeff)
##############################################################################
sub pop2(\@){
  return splice(@{$_[0]},-2);
}	

###########################################################################
#Function to check for a badly presented polynomial  
##############################################################################
sub Errorck{
my (@degree);
@degree=();
(@degree) = @_;
@sortedegree= sort{ $a <=> $b } @degree;
%seen=();
$flag=1;

######Check for repeats###################
foreach $item(@degree){
    unless ($seen{$item}){
       $seen{$item}=1;}
    else{
        $flag=0;
        print"REPEATED INPUT!\n";
        Errormsg();
        FINISH();}}
#####Check for degree from lowest to highest#####
for ($i=0; $i < $#degree; $i++){ 
  if ($sortedegree[$i] < $degree[$i]){        
         print "DEGREES ARE NOT IN ORDER!\n";
         Errormsg();
         $flag= 0;
         FINISH();}}
@degree=();
return $flag;
}
##########################################################
#Function to read in a valid polynomial and store it 
##########################################################
sub Pread{ 
my (@poly)=@_;
my (@POLY);
@POLY=();
foreach $item(@poly){###check each item in poly for nondigits####
 #$abs=abs($item); #abs function gives back 0 for a letter 
 #print"abs=$abs item=$item";
 if($abs =~ /\d/){# \D checks for nondigits also rejects negative numbers
   print"Polynomial has nondigits!\n";
   Errormsg();
   $flag=0;
   FINISH();}}
$headn=shift @poly;
$numnodes=((++$#poly)/2);

#check if first input = number of terms
if ($headn != $numnodes){
  print "FIRST INPUT DOES NOT EQUAL NUMBER OF TERMS!\n";
  Errormsg();
  FINISH();
  $flag=0;}
###########STORAGE###############
    @poly= reverse(@poly);
    for ($i=0; $i < $numnodes; $i++){ 
      @item=pop2(@poly);
      $exp=$item[0];
      $coeff=$item[1];
      if($exp >= 0){
         $POLY[$exp]=$coeff;
         push (@degree,$exp);}
      else{
         print"No negative exponents!\n";
         Errormsg();
         FINISH();}
     }#end for
     push(@POLY,$numnodes);
      @poly=();#ERASE POLY
#######ERROR CHECKING############
$flag= Errorck(@degree);
@degree=();
if ($flag == 0){
      FINISH();}
elsif ($flag == 1){
      return @POLY;}#return pointer to head of the list;
}
###########################################################
#Function to Exit program
###########################################################
sub FINISH{
die print"GOOD BYE\n";
}
###########################################################
#report polynomial with head node X,n,e1,c1,e2,c2,....en,cn
###########################################################
sub Pwrite{
my ($poly)=@_;
for ($i=0;$i<$#$poly;$i++){
  if (($poly->[$i]) != 0){
     print"$poly->[$i]x^$i ";}}
     print"\n";
}
###########################################################
#Function to add two polynomials
###########################################################
sub Padd {
my ($x,$y)= @_;
my @result;
#print "In ADD x=$x->[0] y= $y->[0] last x = $#$x and $#$y\n";

if($#$x<$#$y){
     $min=$#$x;	
     $max=$#$y;}
else{ 
     $min=$#$y;
     $max=$#$x;}
for($i=0; $i<$min;$i++){
     $result[$i] = $x->[$i] + $y->[$i];
     }
for($j=$min+1;$j<$max;$j++){
     $result[$j] = $x->[$j] + $y->[$j];
     }
#print"In ADD result is @result\n";
push(@result,0);
return @result;
}#to compute Z=X+Y and report Z
####################################################
#Function to subtract two polynomials
####################################################
sub Psub{
my($x,$y)=@_;
my @result;
#print "Psub polyA = $x->[0] Psub polyB = $y->[0] last =$#$x and $#$y\n";
if($#$x<$#$y){
   $min=$#$x;
   $max=$#$y;}
else{
   $min=$#$y;
   $max=$#$x;}
for($i=0; $i<$min;$i++){
   $result[$i] =$x->[$i] - $y->[$i];
   }
for($j=$min+1;$j<$max;$j++){
   $result[$j] = $x->[$j] - $y->[$j];
    }
push(@result,0);
return @result;
}
######################################################################
#Function to multiply 2 polynomials
#######################################################################
sub Pmult{
my($x,$y)=@_;
my @result;
#print"Pmult polya=$x->[0] polyb=$y->[0]";

for($p=0;$p<$#$x;$p++){
for($i=0;$i<$#$y;$i++){
$j=$p+$i;
$result[$j] += $x->[$p] * $y->[$i];}}
push(@result,0);
return @result;
}#to compute Z=X*Y and report Z 

########################################################################
#polynomial x is evaluated using real number $a and a result is returned
########################################################################
sub Peval{
my ($result);
my($poly,$a)=@_;
#print"poly is @$poly, value is $a; for counter is $#$poly \n";
for($i=0; $i < $#$poly ; $i++){
    if ($poly->[$i] > 0){
        $result +=$poly->[$i]*($a**$i);}}
return $result; }  
#######################################################################
#Function to erase a poly
########################################################################
sub Perase{
@poly= @_;
for($i=0;$i < $#poly+1;$i++){
$poly[$i]=0;} 
}#return the circular list X to the list  of avaliable spaces
#ReadCommand-to read command line.single command READ,WRITE,ADD,SUB,MULT,ERASE
#EVALUATE,and FINISH
##########################################################################
##############################MAIN PROGRAM################################

$flag=1;
while($flag){
print "TYPE IN A COMMAND\n";
$AorB=0;
@poly=();
$poly = (<STDIN>);
chomp $poly; 
@poly= split(/ /,$poly);
$command = shift (@poly);
$command =~ tr/A-Z/a-z/;

       if($command eq "read") {
           @Poly=Pread(@poly);    
           print "Name this polynomial (A or B):";
           $AorB=(<STDIN>);
           chomp $AorB;
           $AorB =~ s/\W.*//;#delete everything after first word
           $AorB =~ tr/A-Z/a-z/;#lowercase everything
           if ($AorB eq "a"){
              @polyA=();
              @polyA=@Poly;
              @Poly=();
              print "Polynomial A =";
              Pwrite(\@polyA);}
           elsif ($AorB eq "b"){
              @polyB=();
              @polyB=@Poly;
              print "Polynomial B =";
              Pwrite(\@polyB);
              @Poly=();}
           else{
              print"Name poly either A or B!\n";}   
   #print"PolyA = @polyA ,PolyB = @polyB  global poly=@Poly\n";
        }
	elsif($command eq "write") {
          $AorB= shift(@poly); 
          $AorB =~ s/\W.*//;
          $AorB =~ tr/A-Z/a-z/;
          if($AorB eq "a"){
              Pwrite(\@polyA);
              next;} 
          if($AorB eq "b"){
              Pwrite(\@polyB);
              next;} 
          if($AorB eq "c"){
              Pwrite(\@polyC);
              next; }
          else{
              print "Not a valid option. write (a,b,or c).\n";}
        }
    	elsif($command eq "add") {
             $AorB=shift(@poly);
             $AorB=~s/\W.*//;
             $AorB=~ tr/A-Z/a-z/;
             if ($AorB eq "a" || "b"){
                @polyC=Padd(\@polyA,\@polyB);
                 print"PolyC=";
                 Pwrite(\@polyC);         
                 print"\n";}
             else{
               print "Must add a,b\n";} 
        }
	elsif ($command eq "sub") {
           $AorB=shift (@poly);
           $minusAorB= shift(@poly); 
           $AorB =~ tr/A-Z/a-z/;
           $minus =~ tr/A-Z/a-z/;  
           if($AorB eq "a" && $minusAorB eq "b"){
               @polyC=Psub(\@polyA,\@polyB);
               print"PolyC =";
               Pwrite(\@polyC); 
              print"\n";}
           elsif($AorB eq "b" && $minusAorB eq "a"){
               @polyC=Psub(\@polyB,\@polyA);
               print"PolyC = "; 
               Pwrite(\@polyC);
               print "\n";}
           else{
               print "Options: Sub (a b) or (b a)\n";}	
        }
 	elsif ($command eq "mult") {
           @polyC= Pmult(\@polyA,\@polyB);
           print"PolyC =";
           Pwrite(\@polyC);        	
           print"\n";
         }
	elsif ($command eq "erase") {
	    $AorB=shift(@poly); 
            $AorB =~ tr/A-Z/a-z/;
            $AorB =~ s/\W.*//;
            if($AorB eq "a"){
              Perase(@polyA);
              print"Polynomial [$AorB] has been erased.\n"; 
              next;}
            if($AorB eq "b"){
              Perase(@polyB); 
              print"Polynomial [$AorB] has been erased.\n"; 
              next;}
            else{
              print"Erase A or B\n"; } 
        }
	elsif ($command eq "eval") {
          $AorB=shift(@poly);
          if ($AorB eq "a"){
             $result=0;
             print "Evaluate with what number?\n"; 
             $a=(<STDIN>);
             chomp $a;
             $result=Peval(\@polyA,$a);
             print"result = $result \n";
             next;}
          if ($AorB eq "b"){
             print "Evaluate with what number?";
             $a=(<STDIN>);
             chomp $a; 
             $result=Peval(\@polyB,$a);
             print"result = $result\n";
             #memoize 'Peval';
             #$result=Peval(\@polyB,$a);
             #print"Peval=$result \n"; 
             next;}	
          else{
             print"Evaluate A or B?\n";} 
        }
	elsif($command eq "finish") {
             #$flag=0;
             FINISH();
             $flag=0;
        }
	else{
        print "Commands:READ,WRITE,MULT,ADD,SUB,EVAL,ERASE or FINISH.\n";
	}
        redo;
}
