博客

一般我们所输入的四则运算都是中缀四则运算，如：9+(3-1)*3+10/2，为了便于计算机处理，在计算四则运算的时候，往往先将中缀四则运算改为后缀四则运算。

这里 先介绍下后缀四则运算的原理，主要是运用了栈的后进先出，这里首先需要一个栈用来保存运算符：

中缀转后缀的原理：

首先是9，直接保存到数组中，然后是+，直接进栈，然后是（，直接进栈，再就是3，保存到数组中，然后是-，因为栈顶为（，所以直接进栈，然后是），此时从栈顶开始依次将符号保存到数组中，直到遇到（为止，然后是*，因为此时栈中只有+，优先级低于*，所以*直接进栈，然后是3，直接进入数组，然后是+，因为本栈中不可能还有比+更低的优先级了，所以先从栈顶开始将符号保存到数组，然后将+进栈，然后是10，直接进数组，再就是/，由于栈中此时只有+，所以直接进栈，然后是2，直接进数组，最后将栈中的符号从栈顶开始依次保存到数组中，此时得到的后缀表达式结果为：9  3 1 – 3 *+ 10 2 /+

注意事项：

1.数字直接进入保存后缀结果的数组中；

2.遇到‘（’,直接保存到栈中；

3.遇到‘）’,则依次遍历栈中的符号，并保存到数组中，知道遇到’（’为止，且’（’不用保存到数组中；

4.加入符号进栈的规则是：如果栈中的优先级不低于当前符号的优先级，则先将栈中的符号出栈，并保存到数组，然后将当前符号进栈；否则，直接进栈。

计算机计算后缀表达式的原理

：

前面我们得到的后缀表达式为：9  3 1 – 3 *+ 10 2 /+。在中缀转后缀的过程中，我们是将符号存在栈中，这里计算后缀表达式则是将数字保存在栈中，还是运用了栈的后进先出原理。

第一个数字是9，直接进栈，然后是3，直接进栈，数字1，直接进栈，然后是符号’-‘，这里则取出战中的栈顶的数字和栈顶下面的数字，然后用栈顶下面的数字3，减去栈顶的数字1，得到2，然后将之前的栈顶下移，然后保存2，此时栈中保存9  2，然后是3，直接进栈，此时栈中保存9  2  3；然后是*，此时取出2和3，用2*3，得到6，然后将栈顶下移一位，保存6，栈中保存9  6，然后是+，此时取出9和6，得到15，将栈顶下移一位，保存15，此时栈中只有15，再是10，直接进栈，然后是2，直接进栈，此时栈中保存15   10   2，然后是’/’，取出栈中的10和2，用10除以2，得到5，然后栈顶下移一位，保存5，最后栈中保存15   5，最后是符号+，取出栈中15和5，用15加上5，得到10，然后将栈顶下移一位，保存20，最后20是最终结果。

注意事项：

1.数字直接进栈；

2.遇到符号，取出栈中的前两位，用上一位和栈顶进行运算，然后栈中保存结果到上一位，栈顶下移一位；

3.最后栈顶的结果就是最后结果。

下面提供一个程序代码：

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 99

//将中缀表达式转换成后缀表达式
void translate(char str[], char exp[])//将中缀表达式转换为后缀表达式
{
	struct 
	{
		char data[MaxSize];
		int top; //top为栈顶
	}op;
	char ch;
	int i = 0;
	int t = 0;
	op.top = -1;
	ch = str[i];
	i++;
	while (ch != '\0')
	{
		switch (ch)
		{
		case '(':
			op.top++;
			op.data[op.top] = ch;
			break;
		case ')':
			while (op.data[op.top] != '(')
			{
				exp[t] = op.data[op.top];
				t++;
				op.top--;
			}
			op.top--;
			break;
		case '+':
		case '-':
			while (op.top != -1 && op.data[op.top] != '(')
			{
				exp[t] = op.data[op.top];
				op.top--;
				t++;
			}
			op.top++;
			op.data[op.top] = ch;
			break;
		case '*':
		case '/':
			while (op.top != -1 && (op.data[op.top] == '/' || op.data[op.top] == '*'))
			{
				exp[t] = op.data[op.top];
				op.top--;
				t++;
			}
			op.top++;
			op.data[op.top] = ch;
			break;
		case ' ':  //忽略空隔，排除误操作
			break;
		default:
			while (ch >= '0' && ch <= '9')
			{
				exp[t] = ch;
				t++;
				ch = str[i];
				i++;
			}
			i--;
			exp[t] = '#';//分隔符，分隔操作数
			t++;	
		}
		ch = str[i];
		i++;
	}
	//得到剩下部分
	while (op.top != -1)
	{
	     exp[t] = op.data[op.top];
	     t++;
	     op.top--;
	}
	exp[t] = '\0';
}

//计算机计算后缀表达式
float cal_value(char exp[])
{
	struct 
	{
	    float data[MaxSize];
	    int top;
	}st;       //操作数
	float d;
	char ch;
	int t = 0;
	st.top = -1;
	ch = exp[t];
	t++;
	while (ch != '\0')
	{
		switch (ch)   //运算主体
		{
		case '+':
			st.data[st.top - 1] = st.data[st.top - 1] + st.data[st.top];
			st.top--;
			break;
		case '-':
			st.data[st.top - 1] = st.data[st.top - 1] - st.data[st.top];
			st.top--;
			break;
		case '*':
			st.data[st.top - 1] = st.data[st.top - 1] * st.data[st.top];
			st.top--;
			break;
		case '/':
			if (st.data[st.top] != '0')
			{
				st.data[st.top - 1] = st.data[st.top - 1] / st.data[st.top];
			}
			else
			{
				printf("\n\t除0是错误的！");
			}
			st.top--;
			break;
		default:
			d = 0;
			while (ch >= '0' && ch <= '9')
			{
				d = d * 10 + ch - '0';
				ch = exp[t];
				t++;
			}
			st.top++;
			st.data[st.top] = d;
		}
		ch = exp[t];
		t++;
	}
	return st.data[st.top];
}
int _tmain(int argc, _TCHAR* argv[])
{
	char str[MaxSize], exp[MaxSize];
	printf("请输入一个求值表达式：\n");
	gets_s(str);
	printf("原表达式是：%s\n", str);
	translate(str, exp);
	printf("后缀表达式为：%s\n", exp);
	printf("计算后的结果为：%f\n", cal_value(exp));
	system("pause");
	return 0;
}