Bạn đã cân nhắc sử dụng cấu trúc dữ liệu Stack để ghi lại "các điểm nhảy" (tức là vị trí của con trỏ chỉ dẫn).
Vì vậy, về cơ bản, mỗi khi bạn gặp "[", bạn đẩy vị trí hiện tại của con trỏ hướng dẫn trên ngăn xếp này. Bất cứ khi nào bạn gặp phải một "]" bạn đặt lại con trỏ chỉ dẫn đến giá trị hiện đang ở trên cùng của ngăn xếp. Khi một vòng lặp hoàn tất, bạn bật nó ra khỏi ngăn xếp.
Đây là một ví dụ trong C++ với 100 ô bộ nhớ. Mã này xử lý vòng lồng nhau một cách đệ quy và mặc dù nó không được tinh chế nó nên minh họa cho khái niệm ..
char cells[100] = {0}; // define 100 memory cells
char* cell = cells; // set memory pointer to first cell
char* ip = 0; // define variable used as "instruction pointer"
void interpret(static char* program, int* stack, int sp)
{
int tmp;
if(ip == 0) // if the instruction pointer hasn't been initialized
ip = program; // now would be a good time
while(*ip) // this runs for as long as there is valid brainF**k 'code'
{
if(*ip == ',')
*cell = getch();
else if(*ip == '.')
putch(*cell);
else if(*ip == '>')
cell++;
else if(*ip == '<')
cell--;
else if(*ip == '+')
*cell = *cell + 1;
else if(*ip == '-')
*cell = *cell - 1;
else if(*ip == '[')
{
stack[sp+1] = ip - program;
*ip++;
while(*cell != 0)
{
interpret(program, stack, sp + 1);
}
tmp = sp + 1;
while((tmp >= (sp + 1)) || *ip != ']')
{
*ip++;
if(*ip == '[')
stack[++tmp] = ip - program;
else if(*ip == ']')
tmp--;
}
}
else if(*ip == ']')
{
ip = program + stack[sp] + 1;
break;
}
*ip++; // advance instruction
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int stack[100] = {0}; // use a stack of 100 levels, modeled using a simple array
interpret(",>,>++++++++[<------<------>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>>>++++++[<++++++++>-],<.>.", stack, 0);
return 0;
}
EDIT Tôi chỉ đi qua mã một lần nữa và tôi nhận ra rằng có một lỗi trong vòng lặp while mà có 'bỏ qua' vòng phân tích cú pháp nếu giá trị của con trỏ là 0. Đây là nơi tôi thực hiện thay đổi:
while((tmp >= (sp + 1)) || *ip != ']') // the bug was tmp > (sp + 1)
{
ip++;
if(*ip == '[')
stack[++tmp] = ip - program;
else if(*ip == ']')
tmp--;
}
Dưới đây là một thực hiện các phân tích cú pháp tương tự, nhưng mà không sử dụng đệ quy:
char cells[100] = {0};
void interpret(static char* program)
{
int cnt; // cnt is a counter that is going to be used
// only when parsing 0-loops
int stack[100] = {0}; // create a stack, 100 levels deep - modeled
// using a simple array - and initialized to 0
int sp = 0; // sp is going to be used as a 'stack pointer'
char* ip = program; // ip is going to be used as instruction pointer
// and it is initialized at the beginning or program
char* cell = cells; // cell is the pointer to the 'current' memory cell
// and as such, it is initialized to the first
// memory cell
while(*ip) // as long as ip point to 'valid code' keep going
{
if(*ip == ',')
*cell = getch();
else if(*ip == '.')
putch(*cell);
else if(*ip == '>')
cell++;
else if(*ip == '<')
cell--;
else if(*ip == '+')
*cell = *cell + 1;
else if(*ip == '-')
*cell = *cell - 1;
else if(*ip == '[')
{
if(stack[sp] != ip - program)
stack[++sp] = ip - program;
*ip++;
if(*cell != 0)
continue;
else
{
cnt = 1;
while((cnt > 0) || *ip != ']')
{
*ip++;
if(*ip == '[')
cnt++;
else if(*ip == ']')
cnt--;
}
sp--;
}
}else if(*ip == ']')
{
ip = program + stack[sp];
continue;
}
*ip++;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
// define our program code here..
char *prg = ",>++++++[<-------->-],[<+>-]<.";
interpret(prg);
return 0;
}
@Gary, vui lòng xem câu trả lời cập nhật cho hai ví dụ triển khai bằng cách sử dụng ngăn xếp để theo dõi 'điểm nhảy'. Việc đầu tiên là đệ quy trong khi thứ hai là lặp đi lặp lại nhưng cả hai đều làm điều tương tự. Vui lòng cho tôi biết nếu có điều gì đó không rõ ràng để tôi có thể cố làm rõ! –
Cảm ơn. –