栈结构及其在表达式求值中的应用
栈的基本概念
栈是一种遵循"后进先出"（LIFO, Last In First Out）原则的线性数据结构。这意味着最后压入栈的数据会最先被弹出。常见的操作包括：
- push：将元素压入栈顶
- pop：移除并返回栈顶元素
- top/peek：查看栈顶元素但不移除
- isEmpty：判断栈是否为空
基于数组的栈实现
使用固定大小的数组和一个指向栈顶位置的索引变量即可实现栈。
#define MAX_SIZE 10
typedef struct {
int data[MAX_SIZE];
int topIndex;
} ArrayStack;
// 初始化栈
void initialize(ArrayStack* stack) {
stack->topIndex = -1;
}
// 判断栈是否为空
int isStackEmpty(ArrayStack stack) {
return stack.topIndex == -1;
}
// 判断栈是否已满
int isStackFull(ArrayStack stack) {
return stack.topIndex >= MAX_SIZE - 1;
}
// 压入元素
int push(ArrayStack* stack, int value) {
if (isStackFull(*stack)) return 0;
stack->data[++stack->topIndex] = value;
return 1;
}
// 弹出元素
int pop(ArrayStack* stack) {
if (isStackEmpty(*stack)) {
printf("Error: stack underflow\n");
return -1;
}
return stack->data[stack->topIndex--];
}
// 获取栈顶值
int peek(ArrayStack stack) {
if (isStackEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack.data[stack.topIndex];
}
链式栈的实现方式
利用单向链表构建栈，头节点即为栈顶，所有操作均在头部完成，避免了遍历开销。
typedef struct ListNode {
int val;
struct ListNode* next;
} StackNode;
typedef struct {
StackNode* head;
} LinkedStack;
void initLinkedStack(LinkedStack* s) {
s->head = NULL;
}
int linkedPush(LinkedStack* s, int value) {
StackNode* node = (StackNode*)malloc(sizeof(StackNode));
if (!node) return 0;
node->val = value;
node->next = s->head;
s->head = node;
return 1;
}
int linkedPop(LinkedStack* s) {
if (!s->head) {
printf("Stack empty\n");
return -1;
}
StackNode* temp = s->head;
int value = temp->val;
s->head = temp->next;
free(temp);
return value;
}
栈的实际应用场景
链表逆序处理
通过将链表节点依次压入栈中，再逐个弹出重构指针，可实现链表反转。
void reverseList(ListNode** head) {
if (!(*head)) return;
std::stack<ListNode*> nodeStack;
ListNode* current = *head;
// 所有节点入栈
while (current) {
nodeStack.push(current);
current = current->next;
}
// 重新连接节点
current = nodeStack.top();
nodeStack.pop();
*head = current;
while (!nodeStack.empty()) {
current->next = nodeStack.top();
nodeStack.pop();
current = current->next;
}
current->next = nullptr; // 尾部置空
}
中缀表达式转后缀形式
该过程借助栈来管理运算符优先级，确保输出符合逆波兰记法规则。
- 遇到操作数直接添加到结果字符串
- 左括号 '(' 直接入栈
- 右括号 ')' 持续出栈直至匹配左括号
- 运算符则比较优先级：若当前运算符优先级低于或等于栈顶，则弹出栈顶直到条件满足，然后压入当前运算符
- 表达式扫描结束后，清空剩余运算符
std::string infixToPostfix(const std::string& expr) {
std::stack<char> opStack;
std::string output;
for (size_t i = 0; i < expr.length(); ++i) {
char c = expr[i];
if (isspace(c) || c == ',') continue;
if (isdigit(c)) {
while (i < expr.length() && isdigit(expr[i])) {
output += expr[i++];
}
output += ' ';
--i;
}
else if (c == '(') {
opStack.push(c);
}
else if (c == ')') {
while (!opStack.empty() && opStack.top() != '(') {
output += opStack.top();
opStack.pop();
}
opStack.pop(); // 移除 '('
}
else if (isOperator(c)) {
while (!opStack.empty() && opStack.top() != '(' &&
getWeight(opStack.top()) >= getWeight(c)) {
output += opStack.top();
opStack.pop();
}
opStack.push(c);
}
}
while (!opStack.empty()) {
output += opStack.top();
opStack.pop();
}
return output;
}
后缀表达式求值算法
从左到右扫描表达式，遇数字入栈，遇运算符则取出两个操作数进行计算，并将结果压回栈中。
int evaluatePostfix(const std::string& expr) {
std::stack<int> evalStack;
for (size_t i = 0; i < expr.length(); ++i) {
char c = expr[i];
if (isspace(c) || c == ',') continue;
if (isOperator(c)) {
int b = evalStack.top(); evalStack.pop();
int a = evalStack.top(); evalStack.pop();
int result = applyOp(a, b, c);
evalStack.push(result);
}
else if (isdigit(c)) {
int num = 0;
while (i < expr.length() && isdigit(expr[i])) {
num = num * 10 + (expr[i] - '0');
++i;
}
--i;
evalStack.push(num);
}
}
return evalStack.top();
}
完整表达式解析程序框架
整合上述功能，支持用户输入中缀表达式并输出计算结果。
#include <iostream>
#include <stack>
#include <cctype>
#include <string>
bool isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
bool isOperand(char c) {
return std::isdigit(c);
}
int getWeight(char op) {
switch (op) {
case '+':
case '-': return 1;
case '*':
case '/': return 2;
default: return 0;
}
}
bool hasHigherPrecedence(char op1, char op2) {
return getWeight(op1) > getWeight(op2);
}
int applyOp(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default: throw std::invalid_argument("Invalid operator");
}
}
// 此处省略infixToPostfix和evaluatePostfix函数定义
int main() {
std::string input;
std::cout << "Enter expression: ";
std::getline(std::cin, input);
try {
std::string postfix = infixToPostfix(input);
int result = evaluatePostfix(postfix);
std::cout << "Result: " << result << std::endl;
} catch (...) {
std::cerr << "Invalid expression.\n";
}
return 0;
}
