/* Bai tap 3_52 - In bieu thuc dang hau to cua mot bieu thuc trung to */
#include <stdio.h>
#include <conio.h>

#define MAX 100

#define PLUS 0 /* Dau cong */
#define MINUS 1 /* Dau tru */
#define MULTIPLE 2 /* Dau nhan */
#define DIVIDE 3 /* Dau chia */
#define LPAREN 4 /* Dau mo ngoac don */
#define RPAREN 5 /* Dau dong ngoac don */

int top;

struct {
int toantu;
} stack[MAX];

void push (int tt)
{
if (top < MAX-1)
stack[++top].toantu = tt;
}

int isempty()
{
return top == -1;
}

int pop (int *tt)
{
if (!isempty())
{
*tt = stack[top--].toantu;
return 1;
}
return 0;
}

int get (int *tt)
{
if (!isempty())
{
*tt = stack[top].toantu;
return 1;
}
return 0;
}

void xet(int tt)
{
char chuoi[] = "+-*/";
int uutien[] = {0,0,1,1,-1,-1};
int toantu, done = 0, val;

if (isempty())
push(tt);
else
{
do {
if (get(&toantu))
{
if (uutien[tt] <= uutien[toantu])
{
pop(&toantu);
printf("%c ", chuoi[toantu]);
}
else
{
push(tt);
done = 1;
}
}
else
{
done = 1;
push(tt);
}
} while (!done);
}
}

void in_hauto(char *expr)
{
int len, i=0, ttu, done;
char c, chuoi[]="+-*/";
top = -1;
len = strlen(expr);
do {
c = expr[i++];
while (c == ' ' && i < len-1)
c = expr[i++];
switch (c)
{
case '0' :
case '1' :
case '2' :
case '3' :
case '4' :
case '5' :
case '6' :
case '7' :
case '8' :
case '9' : printf("%c ", c); break;
case '+' : xet(PLUS); break;
case '-' : xet(MINUS); break;
case '*' : xet(MULTIPLE); break;
case '/' : xet(DIVIDE); break;
case '(' : push(LPAREN); break;
case ')' : done = 0;
do {
if (isempty())
{
done = 1;
printf("\n\nError\n");
}
else
{
pop(&ttu);
if (ttu != LPAREN)
printf("%c ", chuoi[ttu]);
else
done = 1;
}
} while (!done);
break;
}
} while (i < len);
while (!isempty())
{
pop(&ttu);
printf("%c ", chuoi[ttu]);
}
}

void main()
{
char expr[50];
int done = 0;

printf("\nChuong trinh in bieu thuc hau to tuong ung voi mot bieu thuc"
"trung to hop le"
"\nChu y :"
"\nCac toan hang chi tu 0 den 9"
"\nCac toan tu chi gom + - * / ( )\n");
do {
printf("\nNhap mot bieu thuc trung to hop le (trong de thoat): ");
gets(expr);
if (strlen(expr) > 0)
in_hauto(expr);
else
done = 1;
} while (!done);
}

/* Bai tap 3_34 - Tim phan hieu cua hai danh sach lien ket */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>

typedef struct tagsl {
int key;
struct tagsl *next;
} SL;

SL *L1, *L2, *L;

void initialize()
{
L1 = L2 = L = NULL;
clrscr();
randomize();
}

void cleanup()
{
SL *f;

while (L1 != NULL)
{
f = L1;
L1 = L1->next;
free(f);
}
while (L2 != NULL)
{
f = L2;
L2 = L2->next;
free(f);
}
while (L != NULL)
{
f = L;
L = L->next;
free(f);
}
L1 = L2 = L = NULL;
}

void insert(SL **l, int key)
{
SL *s, *a, *b;

s = (SL *)malloc(sizeof(SL));
s->key = key;
s->next = NULL;
if (*l==NULL)
*l = s;
else
{
a = NULL;
b = *l;
while (b!=NULL && b->key < key)
{
a = b;
b = b->next;
}
if (a == NULL)
{
s->next = *l;
*l = s;
}
else
{
a->next = s;
s->next = b;
}
}
}

void inds(SL *l)
{
SL *f;
printf("\nDanh sach : ");
f = l;
while (f != NULL)
{
printf("%3d", f->key);
f = f->next;
}
}

void taods(SL **l)
{
int i, j, trung[50];
for (j=0; j<50; j++)
trung[j] = 0;
i = 0;
while(i<10)
{
do {
j = random(50);
} while(trung[j] == 1);
trung[j] = 1;
insert(l, j);
i++;
}
}

void hieusl(SL *l1, SL *l2, SL **l)
{
while (l1 != NULL && l2 != NULL)
{
while (l2->key < l1->key && l2 != NULL)
l2 = l2->next;
if (l2 != NULL)
{
if (l1->key != l2->key)
{
insert(l, l1->key);
l1 = l1->next;
}
else
{
l1 = l1->next;
l2 = l2->next;
}
}
}
while (l1 != NULL)
{
insert(l, l1->key);
l1 = l1->next;
}
}
/*
if (l1->key < l2->key)
{
insert(l, l1->key);
l1 = l1->next;
}
else if(l1->key > l2->key)
{
insert(l, l2->key);
l2 = l2->next;
}
else if(l1->key == l2->key)
{
insert(l, l1->key);
l2 = l2->next;
l1 = l1->next;
}
}
if (l1 != NULL)
{
while (l1 != NULL)
{
insert(l, l1->key);
l1 = l1->next;
}
}
if (l2 != NULL)
{
while (l2 != NULL)
{
insert(l, l2->key);
l2 = l2->next;
}
*/
void main()
{
initialize();
taods(&L1);
taods(&L2);
inds(L1);
inds(L2);
printf("\nHieu cua danh sach L1 voi L2 = ");
hieusl(L1, L2, &L);
inds(L);
cleanup();
getch();
}

/* Bai tap 3_86 - Tim tat ca cac hoan vi cua mot mang 5 phan tu */
#include <stdio.h>

int mang[5];

void swap (int *x, int *y)
{
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}

void hoanvi(int k)
{
int j;

if (k==1)
{
printf("\n");
for (j=0; j<n; j++)
printf("%d ", mang[j]);
}
else
for (j=k-1; j>=0; j--)
{
swap(&mang[k-1], &mang[j]);
hoanvi(k-1);
swap(&mang[j], &mang[k-1]);
}
}

void main()
{
int i;

for (i=0; i<5; i++)
mang = i;
hoanvi(5);
getch();
}