第4章+栈和队列（修改）.ppt

整型数简单表达式求值 stack_init(opnd); stack_init(optr); push(optr, read_next()); c = read_next(); while (!stack_empty(optr)) { if (c是操作数) { push(opnd, c - 0); c = read_next(); } else { switch(cmp(get_top(optr), c)) { case : /* 栈顶元素优先级低 */ push(optr, c); c = read_next(); break; case : /* 栈顶元素优先级高 */ pop(optr, oper); pop(opnd, b); pop(opnd, a); push(opnd, operate(a, oper, b)); break; case =: pop(optr, a); c = read_next(); break; } } return get_top(opnd); 4.3 栈与递归的实现 栈在函数调用中的作用 过程一 过程二 过程三 过程四 断 点 三 断 点 一 断 点 二 断点一 断点二 断点三 stack 调用子程序 返回断点 程序执行 程序的执行环境 指令段 程序：源程序编译后的指令代码 数据段 字符串常数 char *str=“Hello!\n”; printf(“a=%d, b=%d\n”, a, b); 函数体外定义的全局数据（有初值的数据和没有初值的数据） int a[128]={2， 3， 4}; int b[128], *p; 函数体内的静态数据 static int reg; 动态申请的数据区 malloc, free 堆栈段 函数参数 函数的返回地址 函数体内的auto型变量（static型变量不在栈中分配） 程序执行过程中堆栈的动态变化 函数调用前的处理和调用结束处理 函数内访问函数的参数变量和函数内部auto型变量的方法 子程序的嵌套调用 int ab(int a, int b) { int c; c = a + b; return c; } int abc(int a, int b, int c) { int x, y; x = ab(a, b); y = ab(b, c); return x + y; } 主程序： abc(1, 2, 3); 使用堆栈实现子程序调用 _DATA SEGMENT $SG51 DB x = %d, 0aH, 00H _DATA ENDS _a$ = 8 _b$ = 12 _c$ = -4 _ab PROC NEAR ; 2 : { push ebp mov ebp, esp push ecx ; 3 : int c; ; 4 : c = a + b; mov eax, _a$[ebp] add eax, _b$[ebp] mov _c$[ebp], eax ; 5 : return c; mov eax, _c$[ebp] ; 6 : } mov esp, ebp pop ebp ret _ab ENDP _main PROC NEAR ; 16 : { push ebp mov ebp, esp push ecx ; 17 : int x; ; 19 : x = abc(1, 2, 3); push 3 push 2 push 1 call _abc add esp, 12 mov _x$[ebp], eax ; 21 : printf(x = %d\n, x); mov eax, _x$[ebp] push eax push $SG51 call _printf add esp, 8 ; 23 : return; ; 24 : } mov esp, ebp pop ebp ret _main ENDP _a$ = 8