在C语言中，使用栈实现表达式的求值是一个经典的问题。栈通常用于处理这类问题，因为它能够方便地处理运算符的优先级和结合性。表达式求值的基本思想是利用两个栈，一个用于存储操作数（operand stack），另一个用于存储运算符（operator stack）。
以下是一个简单的示例，展示了如何使用栈进行表达式求值。在这个示例中，我们假设表达式只包含整数、加（+）、减（-）、乘（*）和除（/）运算符，并且运算符的优先级为：乘法和除法高于加法和减法，且从左到右计算。
数据结构定义
首先，我们定义栈的数据结构以及相关的操作函数。
|
#include <stdio.h> |
|
#include <stdlib.h> |
|
#include <string.h> |
|
#include <ctype.h> |
|
|
|
#define MAX_SIZE 100 |
|
|
|
typedef struct { |
|
int top; |
|
unsigned capacity; |
|
int* array; |
|
} Stack; |
|
|
|
Stack* createStack(unsigned capacity) { |
|
Stack* stack = (Stack*) malloc(sizeof(Stack)); |
|
if (!stack) return NULL; |
|
stack->capacity = capacity; |
|
stack->top = -1; |
|
stack->array = (int*) malloc(stack->capacity * sizeof(int)); |
|
return stack; |
|
} |
|
|
|
int isFull(Stack* stack) { |
|
return stack->top == stack->capacity - 1; |
|
} |
|
|
|
int isEmpty(Stack* stack) { |
|
return stack->top == -1; |
|
} |
|
|
|
void push(Stack* stack, int item) { |
|
if (isFull(stack)) |
|
return; |
|
stack->array[++stack->top] = item; |
|
} |
|
|
|
int pop(Stack* stack) { |
|
if (isEmpty(stack)) |
|
return INT_MIN; |
|
return stack->array[stack->top--]; |
|
} |
|
|
|
int peek(Stack* stack) { |
|
if (isEmpty(stack)) |
|
return INT_MIN; |
|
return stack->array[stack->top]; |
|
} |
运算符优先级和结合性
我们需要定义运算符的优先级和结合性。这里，我们简单地将运算符的优先级用整数表示，其中乘法和除法的优先级高于加法和减法。
|
int getPrecedence(char op) { |
|
switch(op) { |
|
case '+': |
|
case '-': |
|
return 1; |
|
case '*': |
|
case '/': |
|
return 2; |
|
default: |
|
return -1; |
|
} |
|
} |
表达式求值函数
现在我们实现一个函数，用于解析和求值给定的表达式。
|
int applyOp(int a, int b, char op) { |
|
switch(op) { |
|
case '+': return a + b; |
|
case '-': return a - b; |
|
case '*': return a * b; |
|
case '/': |
|
if (b != 0) |
|
return a / b; |
|
else { |
|
printf("Error! Division by zero.\n"); |
|
exit(0); |
|
} |
|
default: |
|
return -1; |
|
} |
|
} |
|
|
|
int evaluateExpression(char* exp) { |
|
Stack* values = createStack(MAX_SIZE); |
|
Stack* ops = createStack(MAX_SIZE); |
|
|
|
int i = 0; |
|
while (exp[i]) { |
|
// 跳过空格 |
|
if (isspace(exp[i])) { |
|
i++; |
|
continue; |
|
} |
|
|
|
// 如果是数字，则压入操作数栈 |
|
if (isdigit(exp[i])) { |
|
int val = 0; |
|
// 解析多位数 |
|
while (isdigit(exp[i])) { |
|
val = (val * 10) + (exp[i] - '0'); |
|
i++; |
|
} |
|
i--; // 因为for循环也会增加i，所以需要回退一步 |
|
push(values, val); |
|
} |
|
// 如果是运算符，则根据优先级进行处理 |
|
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') { |
|
while (!isEmpty(ops) && getPrecedence(peek(ops)) >= getPrecedence(exp[i])) { |
|
int val2 = pop(values); |
|
int val1 = pop(values); |
|
char op = pop(ops); |
|
push(values, applyOp(val1, val2, op)); |
|
} |
|
push |
