C语言实现中缀表达式转后缀表达式并计算

本文将介绍如何使用 C 语言实现中缀表达式转后缀表达式，并计算后缀表达式的值。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAXSIZE 100

/*
  操作符栈的基本规则:
  读入一个操作符时，弹出栈顶元素直至发现优先级更低的元素为止。
  除非是在处理一个'）'，否则绝不从栈中弹出'('。遇到'）',
  将栈顶元素弹出并输出直到遇到相应的'('，但该'('只弹出，不输出。
  读入输入的末尾时，若栈非空，依此弹出并输出所有栈元素。
*/

//字母栈的结构
typedef struct CharacterStack {
	//栈数组
	char arr[MAXSIZE];

	//栈长度
	int length;
}Stackcs;

//数字栈的结构
typedef struct NumberStack {
	//数字数组
	int brr[MAXSIZE];

	//栈长度
	int length;
}Stackns;

//判断字母栈是否为空
int isEmpty(Stackcs* s)
{
	return (s->length == 0);
}

//判断数字栈是否为空
int isEmpty(Stackns* s)
{
	return (s->length == 0);
}

//字母栈顶元素
char topcs(Stackcs* s)
{
	//如果栈不为空
	if (!isEmpty(s)) {
		return s->arr[s->length - 1];
	}
}

//获取数字栈栈顶元素
int topns(Stackns* s)
{
	//如果栈不为空
	if (!isEmpty(s)) {
		return s->brr[s->length - 1];
	}
}

//入字母栈
void pushcs(Stackcs* s, char c)
{
	s->arr[s->length++] = c;
}

//入数字栈
void pushns(Stackns* s, double val)
{
	if (!isEmpty(s)) {
		s->brr[s->length++] = val;
	}
}

//出字母栈
void popcs(Stackcs* s)
{
	s->length--;
}

//出数字栈
void popns(Stackns* s)
{
	s->length--;
}

//优先级函数
int getPriority(char operation)
{
	if (operation == '+' || operation == '-') {
		return 0;
	}
	else if (operation == '*' || operation == '/') {
		return 1;
	}
	else if (operation == '(' || operation == ')') {
		return 2;
	}
	else {
		return -1;
	}
}


//转化为后缀表达式
void toPostfix(char expresson[], char postfix[])
{
	Stackcs cs = { 0 };
	int len = 0;

	//对表达式进行遍历
	for (int i = 0; expresson[i]; i++) {
		char ch = expresson[i];
		//如果是数字
		if (isdigit(ch)) {
			//放入后缀表达式
			postfix[len++] = ch;
			postfix[len++] = ' ';
			continue;
		}

		//如果不是数字 那就是操作符
		int pri = getPriority(ch);

		//只要是正常的操作符
		if (pri != -1) {
			//栈为空
			if (isEmpty(&cs)) {
				//操作符入栈
				pushcs(&cs, ch);
			}
			//栈不为空
			else {
				//如果是右括号
				if (ch == ')') {
					//直至栈空之前
					while (!isEmpty(&cs)) {
						//找到左括号

						//弹出一个操作符
						char top = topcs(&cs);
						popcs(&cs);
						if (top != '(') {
							//如果不是做操作符
							//就进入profix数组
							postfix[len++] = top;
							postfix[len++] = ' ';
						}
						//如果是左括号
						//循环结束 就是将左右括号之前的操作符放入
						else {
							break;
						}
					}
				}
				//如果不是右括号
				else {
					//栈不为空 并且栈顶元素不是左括号
					while (!isEmpty(&cs) && topcs(&cs) != '(') {
						//不是括号的操作话
						//看一下栈顶元素
						char top = topcs(&cs);

						//将栈顶元素的优先级和目前拿到手里的操作符的优先级比较
						//当前操作符优先级小于栈顶元素
						if (pri <= getPriority(top)) {
							//该操作符就不放入操作符栈里面
							//而是直接输出
							postfix[len++] = pri;
							postfix[len++] = ' ';

							//并且要弹出栈顶元素
							//直至遇到优先级更低的元素
							popcs(&cs);
						}
					}
					//如果都没有 就将该操作符入栈
					pushcs(&cs, ch);
				}
			}

		}
	}

	//表达式已经遍历完了
	//现在将操作符栈里面的所有操作符弹出即可
	while (!isEmpty(&cs) && topcs(&cs) != '(') {
		char top = topcs(&cs);
		postfix[len++] = top;
		postfix[len++] = ' ';
		popcs(&cs);
	}
}

//计算后缀表达式的值
double evaluate(char postFix[])
{
	Stackns ns = { 0 };
	for (int i = 0; postFix[i]; i++)
	{
		char ch = postFix[i];
		//如果是数字
		if (isdigit(ch)) {
			//放入数字栈里面
			pushns(&ns, ch - '0');
			continue;
		}
		//如果该字符不是空格
		//则该字符是操作符
		if (ch != ' ') {
			//弹出来两个元素进行运算
			double right = topns(&ns);
			popns(&ns);
			//先弹出来的位于表达式的右侧
			//后弹出来的位于表达式的左侧
			double left = topns(&ns);
			popns(&ns);

			//下面开始运算
			//运算完之后结果直接入栈
			switch (ch) {
			case '+':
				pushns(&ns, left + right);
				break;
			case '-':
				pushns(&ns, left - right);
				break;
			case '*':
				pushns(&ns, left * right);
				break;
			case '/':
				pushns(&ns, left / right);
				break;
			}
			
		}
	}

	//返回最后的一个数字
	return topns(&ns);
}

int main()
{
	char expression[1024] = { 0 };
	char postfix[1024] = { 0 };

	//输入expression表达式
	fgets(expression, sizeof(expression), stdin);

	//中缀变后缀
	toPostfix(expression, postfix);

	//限定结果为两位小数
	printf("%.2lf\n", evaluate(postfix));

	//打印后缀表达式
	printf("%s", postfix);
	
	system("pause");
	return 0;
}

代码解释

数据结构:
- CharacterStack 结构体: 用于存储操作符，采用数组实现，包含一个 arr 数组存储字符，和一个 length 整数记录栈的长度。
- NumberStack 结构体: 用于存储数字，采用数组实现，包含一个 brr 数组存储数字，和一个 length 整数记录栈的长度。
函数:
- isEmpty(Stackcs* s): 判断字母栈是否为空，返回 1 表示为空，0 表示不为空。
- isEmpty(Stackns* s): 判断数字栈是否为空，返回 1 表示为空，0 表示不为空。
- topcs(Stackcs* s): 获取字母栈顶元素，返回栈顶元素。
- topns(Stackns* s): 获取数字栈顶元素，返回栈顶元素。
- pushcs(Stackcs* s, char c): 将一个字符压入字母栈。
- pushns(Stackns* s, double val): 将一个数字压入数字栈。
- popcs(Stackcs* s): 从字母栈弹出栈顶元素。
- popns(Stackns* s): 从数字栈弹出栈顶元素。
- getPriority(char operation): 获取操作符的优先级，返回优先级值。
- toPostfix(char expresson[], char postfix[]): 将中缀表达式转换为后缀表达式。
  - 遍历中缀表达式，如果是数字，直接放入后缀表达式，后面加空格。
  - 如果是操作符，根据优先级进行入栈和出栈操作，并将出栈的操作符放入后缀表达式，后面加空格。
- evaluate(char postFix[]): 计算后缀表达式的值。
  - 遍历后缀表达式，如果是数字，压入数字栈。
  - 如果是操作符，从数字栈弹出两个数字，进行运算，并将结果压入数字栈。
  - 最后返回数字栈顶元素。

代码运行示例

输入: 5+23*7
输出:
166.00
5 23 7 * +

代码中的数字后面加空格

在 toPostfix 函数中，当遍历表达式时，如果当前字符是数字，它会被直接放入后缀表达式数组，并且后面加一个空格，这样做的目的是为了在后缀表达式中明确每个数字的边界。例如，如果我们有一个中缀表达式 "5+23*7"，那么在转换为后缀表达式时，数字 "5" 会被放入后缀表达式数组，后面加一个空格，然后数字 "23" 会被放入后缀表达式数组，后面也加一个空格，以此类推。

这样做的好处是，当我们在计算后缀表达式时，可以根据空格来正确解析每个数字。在代码的 evaluate 函数中，当遍历后缀表达式时，每当遇到一个空格，就知道前面的字符是一个完整的数字。因此，我们可以从数字栈中弹出相应的数字，并进行计算操作。

总结

本文介绍了如何使用 C 语言实现中缀表达式转后缀表达式，并计算后缀表达式的值。代码包含详细的注释，解释了每个步骤的原理和实现方式，适合初学者学习和参考。

希望这篇文章对您有所帮助！如果您有任何问题，请随时在评论区留言。