30/09/2018, 18:40

Giúp về Stack và Queue!

Mình có đề bài thế này http://codepad.org/315GRZkl

File Stack.cpp:


    #include <stdio.h>
typedef int item; //kieu du lieu
typedef struct_NODE
{
    item Data; //du lieu
    struct _NODE *Next; //link
} Node;
typedef struct
{
    Node *Top;
} Stack;
 
void Init (Stack*); //khoi tao Stack rong
int IsEmpty(Stack); //kiem tra Stack rong
void Push(Stack*, item); //them phan tu vao Stack
int Peak(Stack); //Lay phan tu o dau Stack nhung khong xoa
int Pop(Stack*); //Loai bo phan tu khoi Stack
void Input (Stack*); //Nhap Stack
void Output(Stack); //Xuat Stack
Node* MakeNode(item x); //Tao 1 Node

 
void Init (Stack* S) //khoi tao Stack rong
{
    S->Top = NULL;
}
 
int IsEmpty(Stack S) //kiem tra Stack rong
{
    return (S.Top == NULL);
}
 

Node* MakeNode(item x) //tao 1 Node
{
    Node *p = new Node;
    p->Next = NULL;
    p->Data = x;
    return p;
}
 
void Push(Stack* S, item x) //them phan tu vao Stack
{
    Node *p = MakeNode(x);
    p->Next = S->Top;
    S->Top = p;
}
 
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return (IsEmpty(S) ? 0 : S.Top->Data);
}
 
int Pop(Stack* S) // Loai bo phan tu khoi Stack
{
    // Prerequisite: S is not empty.

    item x = 0;
    if ( IsEmpty(*S) )
    {
    	printf("
Stack rong");
    } else {
        x = S->Top->Data; //luu lai gia tri
        Node* p = S ->Top ->Next;
    	delete S ->Top;
        S->Top = p; //Xoa phan tu Top
    }
    return x;
}
 
void Input(Stack* S) //nhap danh sach
{
    int i = 0;
    item x;
    do
    {
        printf("Nhap phan tu thu %d: ", ++i);
        scanf("%d", &x);
        if (x) Push(S, x);
    } while(x); //nhap 0 de ket thuc
}
 
void Output(Stack S)
{
    Node *p = S.Top;
    while (p)
    {
        printf("%d	", p->Data);
        p = p->Next;
    }
    printf("
");
}
#ifdef TEST_STACK

int main()
{
    Stack S;
    Init(&S);
    Input(&S);
    Output(S);
 
    if ( IsEmpty(S) )
	printf("
Stack %srong!", (IsEmpty(S) ? "" : "khong "));

	item x;
    printf("
Nhap phan tu can chen vao DS: ");
    scanf("%d", &x);
    
    Push(&S, x);
    Output(S);
    
    printf("
Xoa phan tu trong Stack: ");
    Pop(&S);
    Output(S);

    printf("
Lay noi dung cua phan tu tai dinh Stack:
");
    printf("%d	", Peak(S));
    
    return 0;
}

#endif`

File Queue.cpp:

    #include <stdio.h>
#include <stdlib.h>
// #include <conio.h>
 
typedef int item; //kieu du lieu
typedef struct _NODE
{
    item Data;
    struct _NODE* Next;
} Node;

typedef struct
{
    Node *Front, *Rear; //Node dau va Node cuoi
    int count; //dem so phan tu
} Queue;
 
void Init(Queue*); //khoi tao Queue rong
int IsEmpty(Queue); //kiem tra Queue rong
void Push(Queue*, item); //them phan tu vao cuoi hang doi
item Pop(Queue*); //Loai bo phan tu khoi dau hang doi
item Qfront(Queue); //xem thong tin phan tu dau hang doi 
Node* MakeNode(item); //tao 1 Node
void Input(Queue*); //Nhap 
void Output(Queue); //Xuat 
 
void Init(Queue* Q)
{
    Q->Front = Q->Rear = NULL;
    Q->count = 0;
}
int IsEmpty (Queue Q) //kiem tra Queue rong
{
    return (Q.count == 0);
}
 
Node* MakeNode(item x) //tao 1 Node
{
    Node *p = new Node;
    p->Next = NULL;
    p->Data = x;
    return p;
}

item Qfront(Queue Q) //xem thong tin phan tu dau hang
{
	if ( IsEmpty(Q) ) 
	{
        printf("Hang doi rong!
");
        return 0;
    } else {
		return Q.Front->Data;
    }
}

void Push(Queue* Q, item x) //them phan tu vao cuoi Queue
{
    Node *p = MakeNode(x); //Neu Q rong
    if ( IsEmpty(*Q) ) {
        Q->Front = Q->Rear = p; //dau va cuoi deu tro den P
    } else {
        Q->Rear->Next = p;
        Q->Rear = p;
    }
    ++Q->count; //tang so phan tu len
}
 
item Pop(Queue* Q) //Loai bo phan tu khoi dau hang doi
{
    if ( IsEmpty(*Q) ) {
        printf("Hang doi rong!
");
        return 0;
    } else {
        item x = Q->Front->Data;
        if (Q->count == 1) { //neu co 1 phan tu
            free(Q->Front);
            Init(Q);
        } else {
            Node *p = Q->Front->Next;
            free(Q->Front);
            Q->Front = p;
        }
        --Q->count;
        return x; //tra ve phan tu lay ra
    }
}
 
void Input(Queue* Q) //nhap hang doi
{
    int i = 0;
    item x;
    do
    {
        printf("Nhap phan tu thu %d: ", ++i);
        scanf("%d", &x);
        if (x) Push(Q, x);
    } while(x); //nhap 0 de ket thuc
}
 
void Output(Queue Q)
{
    Node *p = Q.Front;
    while (p)
    {
        printf("%d	", p->Data);
        p = p->Next;
    }
    printf("
");
}

#ifdef TEST_QUEUE
int main()
{
    Queue Q;
    Init(&Q);
    Input(&Q);
    Output(Q);
 
	printf("Queue %srong!
", (IsEmpty(Q) ? "" : "khong "));

	printf("Them phan tu vao Queue");
    item x;
    printf ("
Nhap phan tu can chen vao Queue: ");
    scanf("%d", &x);
    Push(&Q, x);
    Output(Q);

    printf("
Xoa phan tu trong Queue:   ");
    Pop(&Q); 
    Output(Q);

   	printf("
Lay noi dung cua phan tu tai dinh Queue");
   	printf ("
 %d  ", Qfront(Q));
    // getch();
    return 0;
}
#endif



Chạy file Eval.cpp là file chính:

    #include <stdio.h>
#include <stdlib.h>
#include "Queue.cpp"
#include "Stack.cpp"

int eval(Stack* stack, char oper, int prefix) {
	if (stack->size < 2)
		return 0;
	int a = SPop(stack), b = SPop(stack);
	if ( !prefix ) {
		int t = a;
		a = b;
		b = t;
	}

	switch (oper) {
		case '+':
			SPush(stack, a + b);
			break;
		case '-':
			SPush(stack, a - b);
			break;
		case '*':
			SPush(stack, a * b);
			break;
		case '/':
			if (b == 0)
				return 0;
			SPush(stack, a / b);
			break;
	}

	return 1;
}

// Return 0 if the input expression is invalid
int prefix_eval(const char* s, int len, int* result) {
	Stack stack;
	SInit(&stack);
	int i;

	for (i = len - 1; i > -1; --i) {
		switch (s[i]) {
			case '+': case '-': case '*': case '/':
			{
				if ( !eval(&stack, s[i], 1) )
					return 0;
				break;
			}
			default:
			{
				int digit = 0;
				while (s[i] >= '0' && s[i] <= '9') {
					++digit;
					--i;
				}

				if (digit) {
					int j = ++i, number = 0;
					while (digit--) {
						number *= 10;
						number += s[j++] - '0';
					}
					SPush(&stack, number);
				}
			}
		}
	}

	if (stack.size != 1) {
		return 0;
	} else {
		*result = SPop(&stack);
		return 1;
	}
}

int postfix_eval(const char* s, int len, int* result) {
	Stack stack;
	SInit(&stack);
	int i;

	for (i = 0; i < len; ++i) {
		switch (s[i]) {
			case '+': case '-': case '*': case '/':
			{
				if ( !eval(&stack, s[i], 0) )
					return 0;
				break;
			}
			default:
			{
				int number = 0, digit = 0;
				while (s[i] >= '0' && s[i] <= '9') {
					number *= 10;
					number += s[i++] - '0';
					++digit;
				}

				if (digit) {
					--i;
					SPush(&stack, number);
				}
			}
		}
	}

	if (stack.size != 1) {
		return 0;
	} else {
		*result = SPop(&stack);
		return 1;
	}
}

#ifndef TEST_STACK
#ifndef TEST_QUEUE

int main(void) {
	char pre_expr[] = "- * / 15 - 7 + 1 1 3 + 2 + 1 1";
	int result;

	if (prefix_eval(pre_expr, sizeof(pre_expr) - 1, &result)) {
		printf("%d
", result); // Correct Result: 5
	} else {
		printf("Invalid prefix expression
");
	}

	char post_expr[] = "1 2 + 4 * 5 + 3 -";
	if (postfix_eval(post_expr, sizeof(post_expr) - 1, &result)) {
		printf("%d
", result); // Correct Result: 14
	} else {
		printf("Invalid postfix expression
");
	}
	return 0;
}

#endif
#endif



Ai giúp mình còn ý 12 và 13 chưa làm được?

nhatlonggunz viết 20:50 ngày 30/09/2018

Chuyển sang hậu tố thì:

  1. Sách Lê Minh Hoàng đã có nói
  2. http://geeksquiz.com/stack-set-2-infix-to-postfix/
    http://geeksquiz.com/stack-set-4-evaluation-postfix-expression/
Bài liên quan
0