C语言栈的表达式求值讲解-阿里云开发者社区

C语言栈的表达式求值讲解

2024-03-12 41

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： C语言栈的表达式求值讲解

在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 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

C语言栈的表达式求值讲解