Posted on

Huffman coding

[code]
//Originally FOUND in Internet
//by RIT2009061 vikesh iiita

//Author: Ujjal Suttra DHar [CSE’08,RUET]

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

struct node {
int weight;
char value;
const node *child0;
const node *child1;

node( int c, int i ) {
value = c;
weight = i;
child0 = 0;
child1 = 0;
}

node( const node* c0, const node* c1 ) {
value = 0;
weight = c0->weight + c1->weight;
child0 = c0;
child1 = c1;
}

bool operator<( const node &a ) const {
if(weight ==a.weight)
return value>a.value;
else
return weight >a.weight;
}

void traverse(string code="") const{

if ( child0 ) {
child0->traverse( code + ‘0’ );
child1->traverse( code + ‘1’ );
} else {
cout <<" " <<value <<" ";
cout <<weight;
cout <<" " <<code <<endl;
}
}

};

/*
void count_chars( int *counts )
{
for ( int i = 0 ; i <256 ; i++ )
counts[ i ] = 0;

freopen("input.dat","r",stdin);

char c;
while((c=getchar())!=EOF)
counts[c]++;
}

*/

int main()
{

freopen("input.dat","r",stdin);

int counts[ 256 ];
char a[1000];

gets(a);

for ( int i = 0 ; i <256 ; i++ )
counts[ i ] = 0;

for(int i=0;i<strlen(a);i++)
counts[a[i]]++;

priority_queue < node > q;

for (int i = 0 ; i <256 ; i++ )
if ( counts[ i ] )
q.push( node( i, counts[ i ] ) );

//if you wanna show the queue
/*while(!q.empty()){
cout<<q.top().value<<endl;
q.pop();
}
*/

while ( q.size() >1 ) {
node *child0 = new node( q.top() );
q.pop();
node *child1 = new node( q.top() );
q.pop();
q.push( node( child0, child1 ) );
}

cout <<"CHAR FREQUENCY HOFFMAN-CODE" <<endl;
q.top().traverse();
return 0;
}

[/code]

Posted on

BigInt by Jan vai

/**
*Author : Jan
*Problem Name : Big int for contest
*Algorithm :
*Complexity :
**/

#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include<iostream>
using namespace std;

struct Bigint {
string a;
int sign;

Bigint() {}
Bigint( string b ) { (*this) = b; }
int size() { return a.size(); }
Bigint inverseSign() { sign *= -1; return (*this); }
Bigint normalize( int newSign ) {
sign = newSign;
for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- ) a.erase(a.begin() + i);
if( a.size() == 1 && a[0] == '0' ) sign = 1;
return (*this);
}
void operator = ( string b ) {
a = b[0] == '-' ? b.substr(1) : b;
reverse( a.begin(), a.end() );
this->normalize( b[0] == '-' ? -1 : 1 );
}
bool operator < ( const Bigint &b ) const {
if( a.size() != b.a.size() ) return a.size() < b.a.size();
for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] ) return a[i] < b.a[i];
return false;
}
Bigint operator + ( Bigint b ) {
if( sign != b.sign ) return (*this) - b.inverseSign();
Bigint c;
for( int i = 0, carry = 0; i < (int)a.size() || i < (int)b.size() || carry; i++ ) {
carry += (i < (int)a.size() ? a[i] - 48 : 0) + (i < (int)b.a.size() ? b.a[i] - 48 : 0);
c.a += (carry % 10 + 48);
carry /= 10;
}
return c.normalize(sign);
}
Bigint operator - ( Bigint b ) {
if( sign != b.sign ) return (*this) + b.inverseSign();
if( (*this) < b ) return (b - (*this)).inverseSign();
Bigint c;
for( int i = 0, borrow = 0; i < (int)a.size(); i++ ) {
borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
borrow = borrow >= 0 ? 0 : 1;
}
return c.normalize(sign);
}
Bigint operator * ( Bigint b ) {
Bigint c("0");
for( int i = 0, k = a[i]; i < (int)a.size(); i++, k = a[i] ) {
while(k-- - 48) c = c + b;
b.a.insert(b.a.begin(), '0');
}
return c.normalize(sign * b.sign);
}
Bigint operator / ( Bigint b ) {
if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
Bigint c("0"), d;
for( int j = 0; j < (int)a.size(); j++ ) d.a += "0";
int dSign = sign * b.sign; b.sign = 1;
for( int i = a.size() - 1; i >= 0; i-- ) {
c.a.insert( c.a.begin(), '0');
c = c + a.substr( i, 1 );
while( !( c < b ) ) c = c - b, d.a[i]++;
}
return d.normalize(dSign);
}
Bigint operator % ( Bigint b ) {
if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
Bigint c("0");
int cSign = sign * b.sign; b.sign = 1;
for( int i = a.size() - 1; i >= 0; i-- ) {
c.a.insert( c.a.begin(), '0');
c = c + a.substr( i, 1 );
while( !( c < b ) ) c = c - b;
}
return c.normalize(cSign);
}
void print() {
if( sign == -1 ) putchar('-');
for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
}
};

int main() {

Bigint a, b, c;
string p,q;

cin>>p>>q;
a=p;
b=q;

c = a + b;

c.print();

putchar('\n');

c = a - b;
c.print();
putchar('\n');

c = a * b;
c.print();
putchar('\n');

c = a / b;
c.print();
putchar('\n');

c = a % b;
c.print();
putchar('\n');

return 0;
}
Posted on

JAVA [creating Jar files]

To create a jar file execute this command given below

[code]
jar cf jar-file input-file(s)
[/code]
//input files are .class files and extra files you have used like music,jars etc.

For more you can see this Creating JAR files
After creation you must specify the main class using manifest.

Ways to update a jar file with manifest……
I have created a text file as manifest like aaa.txt which contains

[Code]Main-class: Mainclassname
[/Code]
//a new line or enter must be pressed after Mainclassname before saving

Updating a jar file with main class, you have to move the jar file to the BIN folder of JDK. Then using the command propmt executed the commands given below:

[code]
jar umf aaa.txt calender.jar
jar xvf calender.jar
type META-INFMANIFEST.MF
[/code]
Now double-click on your JAR file….

Thanking you,
Ujjal

Posted on

Stack Implementation in Assembly Language (Algebric expression is correct or not.)

Problem description:
This is a problem in elementary algebra is to decide if a given algebric expression containing several kinds of brackets,such as [,],{,},(,), is correctly bracketed or not.

For example:
(a+[b-{c*(d-e)}]+f) is correctly bracketed but (a+[b-{c*(d-e)]}+f) is not correctly bracketed.

Solution:
This is the case if
(a) There are the same number of left and right bracketes of each kinds,and
(b) When a right bracket appears,the most recent preceeding unmatched left bracket should be of the same type.
This can be decided by using stack. The expression is scanned left to right. When a left bracket is encountered,it is pushed onto the stack. When a right bracket is encountered, the stack is poped (if the stack is empty ,there are too many right brackets) and the brackets are compared. If they are of the same type,the scanning continues.If there is a mismatch,the expression is incorrectly bracketed. At the end of the expression ,if the stack is empty ,the expression is correctly bracketed otherwise there are too many left brackets.
[code]
.model small
.stack 100h
.data

cr equ 0DH ; cr represents carriage return
lf equ 0AH ; lf represents line feed

msg DB cr,lf,’ENTER AN ALGEBRIC EXPRESSION : ‘,cr,lf,’$’
msg_correct DB cr,lf,’EXPRESSION IS CORRECT.$’
msg_left_bracket DB cr,lf,’TOO MANY LEFT BRACKETS. BEGIN AGAIN!’,cr,lf,’$’
msg_right_bracket DB cr,lf,’TOO MANY RIGHT BRACKETS. BEGIN AGAIN!’,cr,lf,’$’
msg_mismatch DB cr,lf,’BRACKET MISMATCH. BEGIN AGAIN!’,cr,lf,’$’
msg_continue DB cr,lf,’Type Y if you want to Continue : ‘,cr,lf,’$’

.code

main proc

mov ax,@data ;get data segment
mov ds,ax ;initialising

start:
lea dx,msg ;user prompt
mov ah,9
int 21h

xor cx,cx ;initializing cx
mov ah,1

input: ;this label for taking input

int 21h

cmp al,0Dh ;checking if the enter is pressed or not
JE end_input

;if left bracket,then push on stack
cmp al, "["
JE push_data
cmp al, "{"
JE push_data
cmp al, "("
JE push_data

;if right bracket,then pop stack

cmp al, ")"
JE parentheses
cmp al, "}"
JE curly_braces
cmp al, "]"
JE line_bracket
jmp input

push_data:
push ax
inc cx
jmp input

parentheses:
dec cx
cmp cx,0
JL many_right

pop dx
cmp dl, "("
JNE mismatch
JMP input

curly_braces:
dec cx
cmp cx,0
JL many_right
pop dx
cmp dl, "{"
JNE mismatch
JMP input

line_bracket:
dec cx
cmp cx, 0
JL many_right
pop dx
cmp dl, "["
JNE mismatch
JMP input

end_input:
cmp cx, 0
JNE many_left

mov ah, 9
lea dx, msg_correct
int 21h

lea dx, msg_continue
int 21h

mov ah,1
int 21h

cmp al, "Y"
JNE exit
JMP start

mismatch:
lea dx, msg_mismatch
mov ah,9
int 21h
JMP start

many_left:
lea dx, msg_left_bracket
mov ah,9
int 21h
JMP start

many_right:
lea dx, msg_right_bracket
mov ah,9
int 21h
JMP start

exit:
mov ah,4ch
int 21h

MAIN ENDP
END MAIN
[/code]

Difficulties & Discussion:
Since I have already solved this problem in C, I hadn’t face too much problem for the algorithm to solve this in assembly language. All dificulties I faced was in the syntax of Assembly language. At first,finishing the code,it wasn’t working for some inputs like (a+b)) or (a+b)} for which output will be “TOO MANY RIGHT BRACKETS”. But my code was being redirected to starting position of main procedure because of my silly mistake.Thsi mistake was in line number 83,94 and 104.

Wrong code
[code] pop dx
dec cx
cmp cx,0
JL many_right
cmp dl, "{"
JNE mismatch
JMP input[/code]
Corrected code:
[code]
dec cx
cmp cx,0
JL many_right
pop dx
cmp dl, "{"
JNE mismatch
JMP input

[/code]

For the example (a+b)}
When the last ‘}’ is scanned,then stack is empty.but in the code I have poped from stack,which is an invalid instruction. But actually it is required that,I will first check if the stack is empty or not.If empty,then “too many right brackets”. If not then pop dx and should be checked with the scanned data.It was done in the right side code.

This problem is an application of stack implementation and we have successfully solved this using stack in assembly language.