Problem 1: Constructing class for infix to postfix conversions



class StackX      //all stack operations
   {
      private int maxSize;
      private char[] stackArray;
      private int top;

      public StackX(int s)       // constructor
             {
	           maxSize = s;
                   stackArray = new char[maxSize];
	           top = -1;
	     }
      
      public void push(char j)  // put item on top of stack
             {     stackArray[++top] = j; }
      
      public char pop()         // take item from top of stack
             {     return stackArray[top--]; }
	
      public char peek()        // what's at top of stack?
             {     return stackArray[top]; }
	
      public boolean isEmpty()  // is stack empty?
             {     
	     	   if (top==-1)
		   return true;
		   else return false;
	     }
		
      public int size()         // return size
             {     return top+1; }
	
      public char peekN(int n)  // return item at index n
             {     return stackArray[n]; }
	
      public void displayStack(String s)
             {
                   System.out.print(s);
	           System.out.print("Stack (bottom-->top): ");
	           for(int j = 0; j < size(); j++)
	           {
	                     System.out.print( peekN(j) );
	                     System.out.print(' ');
		   }
                  System.out.println("");
             }
}  // end class StackX

class InToPost                  // infix to postfix conversion
{
     private StackX theStack;
     private String input;
     private String output = "";
     public InToPost(String in)   // constructor
            {
                   input = in;
                   int stackSize = input.length();
	           theStack = new StackX(stackSize);
	    }

     public String doTrans()      // do translation to postfix
            {
                   for(int j = 0; j < input.length(); j++)      // for each char
                   {
		               char ch = input.charAt(j);            // get it
                               theStack.displayStack("For "+ch+" ");
	                       switch(ch)
		               {
			        case '+':
			        case '-':
		                         gotOper(ch, 1);      
					 break;               //   (precedence 1)
		                case '*':          
		                case '/':
		                         gotOper(ch, 2);     
		                         break;               //   (precedence 2)
			        case '(':               
				         theStack.push(ch); 
			                 break;
			        case ')':              
			                 gotParen(ch); 
					 break;
			        default:                // must be an operand
			                 output = output + " " + ch; // write it to output
			                 break;
			        }  // end switch
	          }  // end for
	         while( !theStack.isEmpty() )     // pop remaining operators
	           {
                                theStack.displayStack("While ");  
				output = output + theStack.pop(); 
		   }
		theStack.displayStack("End   ");     
		return output;                   // return postfix
	} // end doTrans()
	
public  void gotOper(char opThis, int prec1)
{
      while( !theStack.isEmpty() )
      {
      char opTop = theStack.pop();
      if( opTop == '(' )            // if it's a '('
              {
              theStack.push(opTop);      // restore '('
              break;
	      }
      else                          // it's an operator
	      {
	      int prec2;                 // precedence of new operator
	      if(opTop=='+' || opTop=='-')  
	      prec2 = 1;
	      else
     	      prec2 = 2;
	      if(prec2 < prec1)          // if precedence of new operator is less
	            {
		    theStack.push(opTop);   // save newly-popped op
		    break;
		    }
	      else                       // precedence  of new not less
	            output = output + opTop; 
	      }  
       }  // end while
      theStack.push(opThis);           // push new operator
}  

public  void gotParen(char ch)
{  
      while( !theStack.isEmpty() )
      {
      char chx = theStack.pop();
      if( chx == '(' )           // if popped '('
            break;                 
      else                       // if popped operator
            output = output + chx;  // output it
      }  // end while
}  
}  // end class InToPost





Problem 2: Operating on 100 digit integer values

The algorithm is given with the idea for desgining the appropriate classes.

CLASS DECLARATION
-----------------

class Number{

Linkedlist digits;   //linked list to store digits 
int sign;            //+ve or _ve?
int length;          //how many digits are there?

Number();            //constructor
Number(String str)   //constructor intialising to number given in string format
Number(Number other) //constructor initialising to a given Number

void PrintNumber(Number other) //print the Number in readable format
Number Add(Number other)         //add other to given num
Number Subtract(Number other)    //subtract other from given num
Number Multiply(Number other)    //multiply other 
Number Divide(Number other)      //divide number by other

int Compare(Number other)        //compare the number with other
int Zero()                       //is the number zero?
void Makezero()                  //make the number zero
int Samesign(Mumber other)       // are they of same sign
int Equal(Number other)          //is number equals other
Number add(Number other)            //actual addition
Numerb sub(Number other)	//actual subtraction
void mult(Number other)	//actual multiplication
void div(Number other)	//actual divison

}

*********************************************************************************************
CLASS DEFINITIONS
-----------------

Number Add(Number other)
{
Number result;
if(other is zero) return result;
if(other has same sign as this number) return  add(other); 
else return sub(other);
}

Numebr Subtract(Number other)
{
Number result;
if(other is zero) return result;
if(other has same sign) return sub(other);
else {
return add(other);
}
}

Number add(Number other)
{
int lim;  //no. of times loop should be made
lim=(length>=other.length)?length:other.length; //limited to larger number
for(0 to lim)
{
temp=digits[i]+other.digits[i]+carry;
if(temp>=10) {carry =1; temp-=10;}
else carry=0;
digits[i]=temp;
}
}

Number sub(Number other)
{
newlen=0;
for(0 to length) {
temp=digits[i]-other.digts[i]-borrow;
if(temp<0) { temp+=10; borow=1;}
else borrow=0;
digits[i]=temp;
if(temp) newlen=i+1;
}
length=nerwlen;
if(length==0) signpos=0;
}

Number Multiply(Number other)
{
Number result;
if(other is zero) return result;
for(0 to length) 
if(digits[i]>0)
{
temp.shift10();
temp.mul(digits[i]);
result=result.Add(temp);
}

if(signs are same) result.signpos=0 else result.signpos=1;
return result;
}

void shift10(int power)
{
for(0 to length) digits[i+power]=digits[i];
for(power-1 to 0 ) digits[i]=0;
length+=power;
}

void mul(int k)
{
carry=0;
if(k==0) {
Makezero();
return;
}
lim=length;
for(0 to lim) {
temp=digits[i] *k +carry;
carry=temp/10;
temp=temp%10;
digits[i]=temp;
}
if(carry){
digits[length]=carry;
length++;}
}

/*        Divide module from Brinch Hansen's algorithm    */
Number Divide(Number other) 
{
if(other.Zero()) error; //divison by zero
Number result;
if(!Largerthan(other)) return result; //dividing by a bigger number hence result is zero for ints
copy number to result;
if(other.length==1)
result.quotient(other.digits[0]);
else result.div(other);
if(other.signpos==signpos) result.signpos=0;
else signpos=1;
return result;
}

void quotient(int k)
{
carry=0;
for(length-1 to 0) {
temp=10*carry+digits[i];
digits[i]=temp/k;
if (newlen==0 and digits[i]!=0) newlen =i+1;
carry=temp % k;
}
length=newlen;
}

void div(Number other)
{
Number d(other) , r;
int newlen=0;
copy number to r;
m=other.length;
n=length;
f=10/(other.digits[m-1]+1);
r.product(f);
d.product(f);
for(n-m to 0) {
qt=r.trial(d,k,m);
if(qt==0) {
Digits[k]=0;
continue;
}
Number dq(d);
dq.product(qt);
if(r.smaller(dq,k,m) { qt--;dq=dq.Subtract(d);}
if(newlen==0  and qt!=0 ) newlen=k+1;
digits[k]=qt;
r.differnce(dq,k,m);
}
length=newlen;
}

int trial(Number other, int k, int m) //useful for div()
{
int km=k+m;
int r3, d2;
r3=digits[km]*10+digits[km-1]*10+digits[km-2];
d2=other.digits[m-1]*10+other.digits[m-2];
temp=r3/d2;
if(temp<9) return temp; else return 9;
}

int smaller(Number other, int k int m) //useful for div()
{
int i=m;
for(m to 0)
if (digits[i+k] != other.digits[i]) break;
return digits[i+k] < other.digits[i];
}

void difference(Number other, int k, intm)
{
int borrow=0;
for(0 to m) {
diff=digits[i+k]-other.digits[i]-borrow+10;
digits[i+k]=diff%10;
borrow=1-(diff/10);
}
}
/* finishes divide module */

} //class definition ends

*********************************************************************************************************
Write main module here
----------------------

main()
{
}