Department of Computer Science and Engineering, IIT Kanpur

CS210: Data Structures

Dr. R. K. Ghosh


Home | Notice Board | Instructor | TAs | Students | Assignments | Schedule | Lectures | Resources
Assignment 3
Deadline for submission is 18th August 2002, Midnight


Q1. The base type int can represent intger values between -32768 to 32767. You can use long int also which is represented by 4 bytes storage. But suppose it is needed to represent integers which consists of 100 digits or more, then a package must be developed for integer arithmetic on extended numbers system, where extended numbers may consists of upto 100 decimal digits. Write a Java package for arithmetic on Extended numbers. Use linked list for computer representation of the extended numbers. Your package must allow the following operators +, -, *, /, <, >, ==, >=, <= and also handle negative integers.

Q2. Compiler usually transform a given infix expression into postfix form also known as reverse polish notation. The advantage of doing so is to evaluate the expression by a single left to right scan of the input. You may turn an infix expression into post fix form as follows.

  1. Fully parenthesize the expression
  2. Drop all the opening parntheses
  3. Replace each closing parenthesis by the operator found to the immediate left.

See the example below.

Write a java program to convert a give infix expression into postfix form using stack. You can see the algorithm in a standard text book such as Sahni: Fundamentals of Data Structures.
Don't use predefined Java data structures for stack operations.

Note: Try to write all programs in Java. However, TAs have been instructed to check your programs written in C or C++. But there will be a penalty for submissions not written in Java for this assignment is 20%.




Home | Notice Board | Instructor | TAs | Students | Assignments | Schedule | Lectures | Resources
Page last updated 20 Aug, 2002 by Manish Agarwal