Cho mình hỏi thuật toán lập trình C xử lý dấu ( )

[beatlemania]

Hi, mình mới học C sơ sơ, có 1 bài như thế này nhưng mà viết cứ sai hoài.
Viết 1 chương trình C để tính ra kết quả, số chỉ từ 0 đến 9 ( số có 1 chữ số ), phép tính chỉ gồm + và - và có thêm ngoặc ( ).
Ví dụ: Nhập 1 -> xuất ra 1
Nhập 1+4-3+5 -> xuất ra 7
Nhập (1+4)-(4-7)-> xuất ra 8.

Giải thuật của mình là thêm ( và ) vào chuỗi số, sau đó xóa đi ký tự đầu và xét 1 số, lưu lại rồi lại xóa đến khi gặp ( thì đệ quy lại hàm, gặp ) thì thoát ra nhưng mà viết bị lỗi hoài. Ko biết có anh em nào giúp giùm giải thuật nào đơn giản hơn ko. Cám ơn nhiều :beauty::beauty:

[Vimvq1987]

anh thử google với từ khoá là "thuật toán Balan" hoặc "polish algorithm" :)

[matsushita1610]

Hồi năm nhất có học, quên mất rùi, có nguyên cả cái bài giải cái này lun, không biết để xó nào rùi :brick:

[dungcoivb]

anh thử google với từ khoá là "thuật toán Balan" hoặc "polish algorithm" :)
+1
Ký pháp Balan ngược
Thuộc môn Cấu trúc dữ liệu :byebye:

[te[ss]a]

RPN ..., bài này code bằng C++ thì mất tầm 5-10mins gì đấy, còn C thì mất thời gian hơn tí vì phải xử lý chuỗi + cài stack = tay :)

[LoveNF]

Mới học xong, bạn muốn xin code hay là giải thuật :D

[beatlemania]

Mới học xong, bạn muốn xin code hay là giải thuật :D

Code đi cho nó nhanh :*:*:*

[LoveNF]

#include
#include
#include
#define EMPTY -1
using namespace std;
typedef struct CHAR_STACK
{
char *StkArray;
int StkMax;
int StkTop;
};


int IsEmty(const CHAR_STACK &s);
int IsFull(const CHAR_STACK &s);
int InitStack(CHAR_STACK &s,int MaxItem);
char Push(CHAR_STACK &s,char newitem );
char Pop(CHAR_STACK &s, char &outitem);
char Peek(const CHAR_STACK &s, char &outitem);
void Caculate(char *postfix, int &result);
int Priority(char &e);
void infix2postfix(char *infix, char *postfix);
//Kiem tra Stack rong
int IsEmty(const CHAR_STACK &s)
{
return (s.StkTop == EMPTY ) ? 1: 0;
}
int IsFull(const CHAR_STACK &s)
{
return (s.StkTop == s.StkMax-1 )? 1 : 0;
}
int InitStack(CHAR_STACK &s, int MaxItem)
{
s.StkArray = new char;
if(s.StkArray == NULL)
return 0;
s.StkMax = MaxItem;
s.StkTop = -1;
return 1;
}
char Push(CHAR_STACK &s, char newitem)
{
if ( IsFull(s))
return 0;
s.StkTop++;
s.StkArray[s.StkTop] = newitem;
return 1;
}
char Pop(CHAR_STACK &s, char &outitem)
{
if(IsEmty(s))
return 0;
outitem = s.StkArray[s.StkTop];
s.StkTop--;
return 1;
}
char Peek(const CHAR_STACK &s, char &outitem)
{
if(IsEmty(s));
return 0;
outitem = s.StkArray[s.StkTop];
return 1;
}
//Ky Phap BaLan nguoc
void infix2postfix(char *infix, char *postfix)
{
CHAR_STACK s;
char outitem;
char x;
int i = 0;
int j = 0;
InitStack(s,100);
Push(s,'$');
char str[80];
int n= strlen(infix);
for(i=0; i='1') && (postfix[i] <='9'))
{
postfix=infix[i];
j++;
postfix='\0';
}
if(infix[i]=='(')
Push(s,infix[i]);
if(infix[i]=='+'|| infix[i]=='-'|| infix[i]=='*'|| infix[i]=='/')
{
while(1)
{
Pop(s,x);
if(Priority(x)>= Priority(infix[i]))
{
postfix=x;
j++;
}
else{
Push(s, x);
Push(s, infix[i]);
break;
}
}
}
if(infix[i] == ')' )
{
while(1)
{
Pop(s,x);
if(x=='+'|| x=='-'|| x=='*'|| x=='/'){
postfix=x;
j++;
postfix='\0';
}
else
if (x=='(')
break;
}
}
}
while(!IsEmty(s))
{
Pop(s,outitem);
postfix= outitem;
j++;
}
postfix='\0';
}

typedef struct INT_STACK
{
int *StkArray;
int StkMax;
int StkTop;
};
int InitStack_i(INT_STACK &t, int MaxItem);
int IsEmpty_i(const INT_STACK &t);
int IsFull_i(const INT_STACK &t);
int Peek_i(INT_STACK &t, int &outitem);
int Pop_i(INT_STACK &t, int &outitem);
int Push_i(INT_STACK &t, int newitem);
void output(char *infix, char *postfix);

int InitStack_i(INT_STACK &t, int MaxItem)
{
t.StkArray= new int;
if(t.StkArray == NULL )
return 0;
t.StkMax = MaxItem;
t.StkTop = -1;
return 1 ;
}
int IsEmpty_i(const INT_STACK &t)
{
return (t.StkTop == EMPTY )? 1 : 0;
}
int IsFull_i(const INT_STACK &t)
{
if (t.StkTop==t.StkMax-1)
return 1;
return 0;
}
int Push_i(INT_STACK &t, int newitem)
{
if( IsFull_i(t))
return 0;
t.StkArray[t.StkTop] = newitem;
t.StkTop++;
return 1 ;
}
int Pop_i(INT_STACK &t,int &outitem)
{
if(IsEmpty_i(t))
return 0;
outitem = t.StkArray[t.StkTop];
t.StkTop --;
return 1;
}
int Peek_i(INT_STACK &t, int &outitem)
{
if(IsEmpty_i(t))
return 0;
outitem = t.StkArray[t.StkTop];
return 1;
}

//Kiem tra do uu tien cua cac toan tu
int Priority(char &e)
{
if(e=='(') return 0;
if(e=='$') return 1;
if(e=='+'|| e == '-') return 2 ;
if(e=='*'|| e=='/') return 3;
}
//In ra man hinh bieu thuc duoi dang hau to theo yeu cau de bai
void output(char *infix, char *postfix)
{
cout<<" Enter Infix Expression : " << infix << endl;
cout<<" Postfix Expression is : "<='0'&& postfix[i]<='9')
{
value = postfix[i]- 48;
Push_i(t, value);
}
if(postfix[i]=='+'||postfix[i]=='-'||postfix[i]=='*'||postfix[i]=='/')
{
Pop_i(t, b);
Pop_i(t, a);
switch(postfix[i]){
case'+':
result = a+b;
break;
case '-':
result= a-b;
break;
case '*':
result= a*b;
break;
case '/':
result= a/b;
break;
}
Push_i(t, result);
}
}
}

void main(int agrc,char *argv[])
{
int result;
char *infix=argv[1];
char postfix[100];
infix2postfix(infix, postfix);
output(infix, postfix);
Caculate(postfix, result);
cout<<"Result: "<< result<<endl;
}

Code này của mình viết, bạn chịu khó đọc từ từ, chắc cũng dễ hiểu :byebye:

[beatlemania]

Code này của mình viết, bạn chịu khó đọc từ từ, chắc cũng dễ hiểu :byebye:

Cái này cao quá Bro à , mình chưa học tới. Mình chỉ xử lý + - và số có 1 chữ số thôi. :sad::sad:

[katurat0]

Code này của mình viết, bạn chịu khó đọc từ từ, chắc cũng dễ hiểu :byebye:

code đẹp thế :*

[arkis]

viết biểu thức ra dạng cây nhị phân, rồi đệ quy tính từ từ :D. Làm vầy rõ ràng hơn và không khó đâu

[redmerca]

Code này của mình viết, bạn chịu khó đọc từ từ, chắc cũng dễ hiểu :byebye:

Cái này cũng gọi là code sao :shot:
Không có lấy 1 chút chú thích, không nói người khác mà ngay người viết sau 5 năm 10 năm đọc lại liệu gì đã nhớ :shot:

[leblue]

Cái này cũng gọi là code sao :shot:
Không có lấy 1 chút chú thích, không nói người khác mà ngay người viết sau 5 năm 10 năm đọc lại liệu gì đã nhớ :shot:

Code là code chứ sao :|.
Cơ bản là nắm được ý tưởng, có ý tưởng thì code bựa mấy mà đọc chả hiểu.
Đíu hỉu định nghĩa code của bạn là gì mà phang câu như thế.

[f22_raptor]

Code là code chứ sao :|.
Cơ bản là nắm được ý tưởng, có ý tưởng thì code bựa mấy mà đọc chả hiểu.
Đíu hỉu định nghĩa code của bạn là gì mà phang câu như thế.

Nếu muốn người khác hiểu thì nên comment vào, tốt nhất là như thế
Mấy cái nhỏ nhỏ thì ko comment cũng ko sao chứ lớn lớn ko comment hơi bị căng

[redmerca]

Code là code chứ sao :|.
Cơ bản là nắm được ý tưởng, có ý tưởng thì code bựa mấy mà đọc chả hiểu.
Đíu hỉu định nghĩa code của bạn là gì mà phang câu như thế.

Gọi là mớ bòng bong chắc cũng ko sai :surrender:
Bạn có thấy code trên mạng tải về thường phần comment nó chiếm đến 1 nửa không.
Ý tưởng của bạn người khác có hiểu được không; code dài đến hàng nghìn, chục nghìn dòng không có comment đọc hiểu được không :surrender:

[Dizzy]

Có mỗi thế mà đến cả trăm dòng code. Học lập trình để làm j nhỉ, thuê 1 thằng về tính cho nhanh :D

[trungtintts2008]

Mới học xong, bạn muốn xin code hay là giải thuật :D

Share cho mình giải thuật với đi bạn, :) mình cũng đang vướng vấn đề này, nhìn code thấy đuối quá :ops:

[te[ss]a]

Cái này cao quá Bro à , mình chưa học tới. Mình chỉ xử lý + - và số có 1 chữ số thôi. :sad::sad:

Tặng bạn cái code chỉ xử lý +- & 1 chữ số, cái này chỉ dùng pointer & recursion thông thường, không dùng stack hay cây cối gì cả =p.

#include
#include
#include

char *pb, *b;

char i2p()
{
char *s = (char*)malloc(100);
char *ps; ps = s;
int i;
do
{
if (*pb > 47 && *pb < 59) *(b+i++) = *pb;
if (*pb == '+' || *pb == '-')
{
while (*(ps-1)!= '(' && ps > s)
*(b+i++) = *(--ps);
*ps++=*pb;
}
else if (*pb == '(')
*ps++=*pb;
else if (*pb == ')')
{
while (*(ps-1)!= '(' && ps > s)
*(b+i++) = *(--ps);
ps--;
}
} while (*(++pb) != '\0');
while (ps > s)
*(b+i++) = *(--ps);
*(b+i) = '\0';
pb = b + strlen(b);
}

int eval()
{
int x;
--pb;
if (pb>=b)
switch (*pb)
{
case '+': return eval()+eval();
case '-': return x=eval(),eval()-x;
default: return (*pb-48);
}
}

int main()
{
pb = b = (char*)malloc(100);
scanf("%s", b);
i2p();
printf("%d\n", eval());
return 0;
}


p.s. cái này cũng đơn giản nên chắc không cần comment nhỉ :pudency:

[vipteen]

giờ mới thấy anh em voz hiểu biết rất sâu rộng, hầu như vấn đề nào post lên đều giải quyết dc hết,từ tình cảm, đến văn hóa, hành động, đâm thuê chém mướn:* hic, giá mà mình đến với voz sớm hơn thì điểm thi đại học chắc cao hơn nữa:):):)

[phamthaihoa]

Code là code chứ sao :|.
Cơ bản là nắm được ý tưởng, có ý tưởng thì code bựa mấy mà đọc chả hiểu.
Đíu hỉu định nghĩa code của bạn là gì mà phang câu như thế.

Nông dân -_-

[moneyloving]

giờ mới thấy anh em voz hiểu biết rất sâu rộng, hầu như vấn đề nào post lên đều giải quyết dc hết,từ tình cảm, đến văn hóa, hành động, đâm thuê chém mướn:* hic, giá mà mình đến với voz sớm hơn thì điểm thi đại học chắc cao hơn nữa:):):)

thấp đi thì có-_-

[beatlemania]

a;14001748']Tặng bạn cái code chỉ xử lý +- & 1 chữ số, cái này chỉ dùng pointer & recursion thông thường, không dùng stack hay cây cối gì cả =p.

p.s. cái này cũng đơn giản nên chắc không cần comment nhỉ :pudency:

Thanks Bro nhiều. Mình copy vào máy để test thì vẫn chưa chạy được, ko biết thiếu cái gì. Để mình thử lại :D

[AriesStar]

Thanks Bro nhiều. Mình copy vào máy để test thì vẫn chưa chạy được, ko biết thiếu cái gì. Để mình thử lại :D

post lỗi lên !!!

bác nào viết code không cmt thì nên xem lại !!!

Anh em nhắc là có nguyên nhân cả đó -_-

Mình học thì code phải có cmt ... có cmt mới là code !!! Không có = zero điểm :nosebleed:

[voluptuous]

Code này của mình viết, bạn chịu khó đọc từ từ, chắc cũng dễ hiểu :byebye:
Sao không bỏ dô "code" cho dễ nhìn, bài này mình viết bằng Assembly còn ngắn hơn đó.

[beatƖemania]

@beatlemania: mài học ngành y mà sao học cả C thế :lmao:

bài kiểu này thấy thường được làm minh họa cho cú pháp Ba Lan ngược dùng pull/push stack, nên thôi sẵn tiện học về stack luôn đi :D

[te[ss]a]

Thanks Bro nhiều. Mình copy vào máy để test thì vẫn chưa chạy được, ko biết thiếu cái gì. Để mình thử lại :D

Mình chạy bthường, bro xem lại nhé :)

Còn cái đoạn code ở trên mình viết có vài dòng, bảo mình comment thì mình cũng chả biết comment cái gì. Code viết trong 5mins, chả có gì huyền bí hay cao siêu để comment cả :pudency:

[alerk]

Bài ni ngày xưa học CTDL + GT thầy Bá dạy, dùng cây đa thức thì phải :D
Lười quá lâu rồi ko quay lại ko biết thế nào.

[beatlemania]

a;14015368']Mình chạy bthường, bro xem lại nhé :)

Còn cái đoạn code ở trên mình viết có vài dòng, bảo mình comment thì mình cũng chả biết comment cái gì. Code viết trong 5mins, chả có gì huyền bí hay cao siêu để comment cả :pudency:

Nó báo ko biến malloc và strlen ko tìm đc. Mặc dù có báo thư viện "string.h" nhưng mà ko hiểu sao strlen nó ko chịu. Còn malloc ko biết là tên biến hay là 1 lệnh ???

[beatlemania]

@beatlemania: mài học ngành y mà sao học cả C thế :lmao:

bài kiểu này thấy thường được làm minh họa cho cú pháp Ba Lan ngược dùng pull/push stack, nên thôi sẵn tiện học về stack luôn đi :D

Mình dùng nick của nó thôi Bro, nick mình bị ban rồi :what:. Mình học chuyên ngành bên chế tạo máy, tuy nhiên phải học môn này vì môn này là cơ sở của môn mechatronics sau này. Để thời gian nghiên cứu nó thì cũng ok thôi nhưng mà vì mình ko theo chuyên ngành này mà lại có quá trời môn khác để học nên bí quá :):)

[te[ss]a]

Nó báo ko biến malloc và strlen ko tìm đc. Mặc dù có báo thư viện "string.h" nhưng mà ko hiểu sao strlen nó ko chịu. Còn malloc ko biết là tên biến hay là 1 lệnh ???

malloc là hàm allocate memory (cần stdlib.h)
strlen là hàm lấy string length (cần string.h)

Không biết bro dùng compiler gì chứ đã include 2 cái trên rồi thì không thể báo lỗi được :hang:

Bản không dùng malloc & strlen :pudency:

#include

char *pb, b[100];

int strlen_alt(char *s)
{
char *p = s;
while (*p != '\0') p++;
return p-s;
}

void i2p()
{
char s[100];
char *ps = s;
int i = 0;
do
{
if (*pb > 47 && *pb < 59) *(b+i++) = *pb;
if (*pb == '+' || *pb == '-')
{
while (*(ps-1)!= '(' && ps > s)
*(b+i++) = *(--ps);
*ps++=*pb;
}
else if (*pb == '(')
*ps++=*pb;
else if (*pb == ')')
{
while (*(ps-1)!= '(' && ps > s)
*(b+i++) = *(--ps);
ps--;
}
} while (*(++pb) != '\0');
while (ps > s)
*(b+i++) = *(--ps);
*(b+i) = '\0';
pb = b + strlen_alt(b);
}

int eval()
{
int x;
--pb;
if (pb>=b)
switch (*pb)
{
case '+': return eval()+eval();
case '-': return x=eval(),eval()-x;
default: return (*pb-48);
}
}

int main()
{
pb = b;
scanf("%s", b);
i2p();
printf("%d\n", eval());
return 0;
}

[beatlemania]

a;14022384']malloc là hàm allocate memory (cần stdlib.h)
strlen là hàm lấy string length (cần string.h)

Không biết bro dùng compiler gì chứ đã include 2 cái trên rồi thì không thể báo lỗi được :hang:

Mình dùng Visual Basic. Để mình check lại xem. Anyway cám ơn Bro nhiều nhiều :byebye::byebye::byebye:

[te[ss]a]

Mình dùng Visual Basic. Để mình check lại xem. Anyway cám ơn Bro nhiều nhiều :byebye::byebye::byebye:

Visual Basic thì liên quan gì C :hang:, nhưng mà VC6 thì có thể tại cái vc6 implement C/C++ đần độn lắm :hang:, anyway thì mình up bản không dùng malloc & strlen lên rồi nhưng mà cũng không chắc là chạy đúng với VC6 đâu -_-

[beatlemania]

a;14022952']Visual Basic thì liên quan gì C :hang:, nhưng mà VC6 thì có thể tại cái vc6 implement C/C++ đần độn lắm :hang:, anyway thì mình up bản không dùng malloc & strlen lên rồi nhưng mà cũng không chắc là chạy đúng với VC6 đâu -_-

Ý nhầm :-j. Ý mình là Visual Studio 2008 sorry Bro. Ko biết thế nào là đi viết là VB :surrender::surrender:

Cái malloc mình chưa học nên cũng ko hiểu nguyên lý của nó lắm :-s

[te[ss]a]

Ý nhầm :-j. Ý mình là Visual Studio 2008 sorry Bro. Ko biết thế nào là đi viết là VB :surrender::surrender:

Cái malloc mình chưa học nên cũng ko hiểu nguyên lý của nó lắm :-s

Mình compile bằng VS2008 hoàn toàn bình thường :pudency:

http://vozforums.com/attachment.php?attachmentid=182260&stc=1&d=1272719123

Tặng bạn cái solution VS2008 luôn =p

[beatlemania]

Vẫn ko chạy được, chả hiểu nữa :((...
Ko biết có phải mình dùng Win64 ko nên thấy thằng VS này hay bị problem lắm...

/ps: Bro có code nào ko dùng malloc ko, tại cái này mình chưa học. Vì khi nộp bài phải giải thích nữa giải thuật mới cho điểm :(

[te[ss]a]

Trang trước mình có up 1 cái code không dùng malloc với strlen đấy, bạn xem kỹ lại nhé ._.

a;14022384']malloc là hàm allocate memory (cần stdlib.h)
strlen là hàm lấy string length (cần string.h)

Không biết bro dùng compiler gì chứ đã include 2 cái trên rồi thì không thể báo lỗi được :hang:

Bản không dùng malloc & strlen :pudency:

#include

char *pb, b[100];

int strlen_alt(char *s)
{
char *p = s;
while (*p != '\0') p++;
return p-s;
}

void i2p()
{
char s[100];
char *ps = s;
int i = 0;
do
{
if (*pb > 47 && *pb < 59) *(b+i++) = *pb;
if (*pb == '+' || *pb == '-')
{
while (*(ps-1)!= '(' && ps > s)
*(b+i++) = *(--ps);
*ps++=*pb;
}
else if (*pb == '(')
*ps++=*pb;
else if (*pb == ')')
{
while (*(ps-1)!= '(' && ps > s)
*(b+i++) = *(--ps);
ps--;
}
} while (*(++pb) != '\0');
while (ps > s)
*(b+i++) = *(--ps);
*(b+i) = '\0';
pb = b + strlen_alt(b);
}

int eval()
{
int x;
--pb;
if (pb>=b)
switch (*pb)
{
case '+': return eval()+eval();
case '-': return x=eval(),eval()-x;
default: return (*pb-48);
}
}

int main()
{
pb = b;
scanf("%s", b);
i2p();
printf("%d\n", eval());
return 0;
}


Giải thuật thì đầu tiên dùng hàm i2p để convert cái b từ dạng infix sang postfix (thuật toán convert thì là shunting yard nhưng mình dùng cái char *s như stack chứ không implement stack), sau đó dùng cái eval để tính giá trị của biểu thức (thuật toán (http://en.wikipedia.org/wiki/Reverse_Polish_notation#Postfix_algorithm) & mình implement bằng đệ quy chứ không dùng stack)

[beatlemania]

Cám ơn bro nhiều lắm. Chạy được rồi. Mình đang ngồi đọc để hiểu thuật toán :byebye: