C语言栈 中缀表达式 函数调用栈

### C语言中栈的数据结构 在C语言中，栈是一种线性数据结构，遵循“后进先出”（LIFO, Last In First Out）的原则。栈只允许在一端进行插入和删除操作，这一端被称为栈顶（Top），另一端被称为栈底（Bottom）。栈的基本操作包括：Push（将元素压入栈顶）、Pop（将栈顶元素弹出）、getTop（查看栈顶元素但不弹出）、IsEmpty（判断栈是否为空）以及IsFull（判断栈是否已满，对于固定大小的栈）[^3]。 以下是使用C语言实现一个简单的栈结构： ```c #define MAX_SIZE 50 typedef struct { int data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s->top = -1; } int isEmpty(Stack *s) { return s->top == -1; } int isFull(Stack *s) { return s->top == MAX_SIZE - 1; } void push(Stack *s, int value) { if (isFull(s)) { printf("Stack Overflow\n"); return; } s->data[++(s->top)] = value; } int pop(Stack *s) { if (isEmpty(s)) { printf("Stack Underflow\n"); return -1; } return s->data[(s->top)--]; } int getTop(Stack *s) { if (isEmpty(s)) { printf("Stack is empty\n"); return -1; } return s->data[s->top]; } ``` ### 中缀表达式的解析 中缀表达式是人类常用的数学表达式形式，例如 `3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3`。为了计算机能够高效地计算中缀表达式的结果，通常需要将其转换为后缀表达式（逆波兰表示法）。后缀表达式没有括号，运算符总是跟在其操作数之后，因此可以利用栈来有效地求值[^1]。 以下是将中缀表达式转换为后缀表达式的算法步骤： 1. 初始化两个栈：一个用于存储操作数，另一个用于存储运算符。 2. 遍历中缀表达式的每个字符： - 如果是操作数，则直接输出到结果字符串。 - 如果是左括号 `(`，则将其压入运算符栈。 - 如果是右括号 `)`，则从运算符栈中弹出运算符并输出，直到遇到左括号。 - 如果是运算符，则比较其与栈顶运算符的优先级。如果栈顶运算符优先级更高或相同，则弹出栈顶运算符并输出，直到栈顶运算符优先级较低为止。然后将当前运算符压入栈。 3. 遍历完成后，将剩余的运算符从栈中弹出并输出。 以下是一个示例代码，展示如何将中缀表达式转换为后缀表达式： ```c #include <stdio.h> #include <ctype.h> #include <string.h> int precedence(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; if (op == '^') return 3; return 0; } void infixToPostfix(char *infix, char *postfix) { Stack s; initStack(&s); int i = 0, j = 0; while (infix[i] != '\0') { if (isdigit(infix[i])) { postfix[j++] = infix[i++]; } else if (infix[i] == '(') { push(&s, infix[i++]); } else if (infix[i] == ')') { while (!isEmpty(&s) && getTop(&s) != '(') { postfix[j++] = pop(&s); } if (!isEmpty(&s) && getTop(&s) != '(') { return; // Invalid expression } else { pop(&s); } i++; } else { while (!isEmpty(&s) && precedence(getTop(&s)) >= precedence(infix[i])) { postfix[j++] = pop(&s); } push(&s, infix[i++]); } } while (!isEmpty(&s)) { postfix[j++] = pop(&s); } postfix[j] = '\0'; } ``` ### 函数调用栈的工作原理 函数调用栈是程序运行时用来管理函数调用的一种数据结构。每当一个函数被调用时，它的相关信息（如返回地址、局部变量等）会被压入栈中。当函数执行完毕后，这些信息会被弹出栈，控制权返回到调用该函数的地方[^4]。 函数调用栈的主要作用包括： - **保存返回地址**：记录函数执行完毕后应返回的位置。 - **保存局部变量**：为函数的局部变量分配存储空间。 - **传递参数**：将调用者提供的参数传递给被调用的函数。 以下是一个简单的函数调用栈示例： ```c #include <stdio.h> void functionB() { printf("Inside functionB\n"); } void functionA() { printf("Inside functionA\n"); functionB(); } int main() { printf("Inside main\n"); functionA(); return 0; } ``` 在上述代码中，程序首先执行 `main` 函数，然后调用 `functionA`，接着调用 `functionB`。每次函数调用时，相关信息都会被压入函数调用栈中。当函数执行完毕后，控制权依次返回到上一层函数。 ###