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?
Bài liên quan
Chuyển sang hậu tố thì:
http://geeksquiz.com/stack-set-4-evaluation-postfix-expression/