表达式求值

中缀表达式：

创新互联坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站制作、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的阳春网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

       把运算符放在参与运算的两个操作数中间的表达式称作中缀表达式例：“3+4*5-6/2”，因为中缀表达式计算时必须按照优先级从左向右计算，所以计算机在进行中缀表达式求值时比较麻烦，而后缀表达式求值比较方便。

后缀表达式：

        把运算符放在参与运算的两个操作数后面的表达式称作后缀表达式。

例：中缀表达式：3+4*5-6/2

       转换成后缀表达式： 3  4  5 * + 6  2  /  -

        中缀表达式：9-8*（4-3）

        转换成后缀表达式： 9   8   4  3  -  *  -

转换规则：

        按照优先级，把每个运算符都移到它的两个操作数的后面，再删除所有的括号

后缀表达式的求值：

        从左向右一次扫描后缀表达式，遇到运算符将将它前面的两个运算数取出并计算，并将结果带入后缀表达式，直到扫描到最后一个后缀表达式。

表达式求值：

       表达式求值是栈应用的一个基本例子，输入一个中缀表达式，求取相应的结果。因为计算机不会算中缀表达式，所以我们先要将中缀表达式转换成相应的后缀表达式再进行计算。要转成相应的后缀表达式，我们应该创建两个栈，一个用来存放操作数，一个用来存放运算符。

中缀表达式求值的算法：

         从左向右扫描中缀表达式，若遇到操作数，则直接压入运算数栈，若遇到符号，则与运算符栈的栈顶元素比较，若读取符号的优先级高，则读取的符号进栈；否则让运算符栈的栈顶符号退栈并且将运算数栈最上面的两个元素退栈，然后将运算的结果压入运算数栈，一直这样循环直到读取的符号的优先级高于运算符栈顶元素。

因为每读取一个符号就要与运算符栈的栈顶元素进行优先级比较，我们不能每次都写一大堆if else语句，所以我们可以将运算符的优先级的结果放到一个二维数组中，然后利用查表法，判断优先级。

因为当我们读取第一个符号时，运算符栈还是个空栈，为了方便比较，我们在栈底压入一个#，并规定#的优先级最低，并将“#”作为表达式输入结束的标志。

为了方便索引：我们再创建一个一维数组，

char arr[7] = { '+' , '-', '*', '/', '(', ')', '#' };通过它来找到栈顶符号和读取符号在优先级数组中的位置。

实现：输入一个合法的中缀表达式，只包含“+ - * /”四种运算符，并以“#”作为结束标志。


//函数声明：

#include
#include

#define STACK_INIT_MEMORY 20               //初始时开辟栈的内存大小
#define STACK_GROW_MEMORY 10               //当栈满时，追加内存的大小

const char arr[7];              //声明一个存放运算符的一维数组，作为索引
void init_priority_list(char list[][7]);      //初始化符号表

typedef struct stack_num            //声明一个存放运算数的结构体类型
{
	int *esp;                //栈顶指针
	int *ebp;                //栈底指针
	int size;                 //记录当前栈空间最多能存几个元素
}stack_num;
void creatstack_num(stack_num *S);          //创建存放运算数的栈
void push_num(stack_num *S, int x);         //将参数x中的数压入运算数栈中
int pop_num(stack_num *S, int *x);         //弹出栈顶元素，并通过形参x带回

typedef struct stackpop_opreation           //声明一个存放运算符的结构体类型
{
	char *esp;                   //栈顶指针
	char *ebp;                   //栈底指针
	int size;                    //记录当前栈空间最多能存几个元素
}stack_operation;
void creatstack_operation(stack_operation *S);      //创建一个存放运算符的栈
void push_operation(stack_operation *S, char symbol);  //将符号压入运算符栈中
int pop_opreation(stack_operation *S, char *top);    //将运算符栈中的栈顶元素弹出




//函数实现：

char judge_priority(stack_operation* S, char c);       //判断读取的运算符与栈顶符号的优先级,并返回
int operation(int a, char symbol, int b);          //对运算数进行相的运算，并将结果返回
int judge_num(char c);          //判断读取的是符号还是数字，如果是数字返回1


#include"expression.h"

const char arr[7] = { '+', '-', '*', '/', '(', ')', '#' };     //通过arr[7]来查找list[][]中的优先级

void init_priority_list(char list[][7])          //初始化优先级列表
{
	int arr2[7] = { 1, 1, 2, 2, 3, 0, -1 };    //列作为栈顶元素，行代表读取的运算符
	for (int i = 0; i < 7; i++)
	{
		for (int j = 0; j < 7; j++)
		{
			if ((i == 4 && j == 5) || (i == 6 && j == 6)  //令'('与‘）’，‘#’与‘#’优先级相同
				list[i][j] = '=';
			else
			{
				if (arr2[i] >= arr2[j])
					list[i][j] = '>';         //栈顶优先级高
				else if (arr2[i] <= arr2[j])
					list[i][j] = '<';     //读取的运算符优先级高
			}

		}
	}
}

void creatstack_num(stack_num *S)              //创建运算数栈
{
	S->ebp = (int *)malloc(sizeof(int)* STACK_INIT_MEMORY);
	if (S->ebp == NULL)           //判断动态内存是否开辟成功
		exit(1);
	S->size = STACK_INIT_MEMORY;             
	S->esp = S->ebp;            //让栈顶指针指向栈底
}
void push_num(stack_num *S, int x)
{
	if (S->esp - S->ebp >= S->size)       //判断当前栈是否已满
	{                         //栈满追加空间
		S->ebp = (int *)realloc(S->ebp, sizeof(int)*(S->size + STACK_GROW_MEMORY));
		if (S->ebp == NULL)
			exit(1);
		S->esp = S->ebp + S->size;  //让栈顶指针向后偏移指向要入栈的位置
		S->size += STACK_GROW_MEMORY;  //更新栈的size
	}
	*S->esp++ = x;
}
int pop_num(stack_num *S, int *x)               
{
	if (S->esp == S->ebp)
		return 0;           //如果是空栈，则返回0
	else
	{
		*x = *--S->esp;
		return 1;                                             //如果弹出成功，返回1，并将弹出的元素保存在x中带回
	}
}




void creatstack_operation(stack_operation *S)           //创建运算符栈
{
	S->ebp = (char *)malloc(sizeof(char)*STACK_INIT_MEMORY);
	if (S->ebp == NULL)
		exit(1);                                               //判断动态内存是否开辟成功
	S->size = STACK_INIT_MEMORY;
	S->esp = S->ebp;
}
void push_operation(stack_operation *S, char symbol)
{
	if (S->esp - S->ebp >= S->size)                            //如果栈满则追加空间
	{
		S->ebp = (char *)realloc(S->ebp, sizeof(char)*(S->size += STACK_GROW_MEMORY));
		if (S->ebp == NULL)
			exit(1);
		S->ebp = S->ebp + S->size - STACK_GROW_MEMORY;
	}
	*S->esp++ = symbol;
}
int pop_opreation(stack_operation *S, char *top)
{
	if (S->esp == S->ebp)
		return 0;                                                                   //如果栈是空栈，则返回0
	else
		*top = *--S->esp;        //否则将弹出的匀速保存在top中带回
	return 1;
}


char judge_priority(stack_operation* S, char c)     //判断栈顶运算符与读取的运算符的优先级
{
	char list[7][7];
	init_priority_list(list);           //初始化优先级表
	int line = 0;                                  
	int row = 0;
	for (line = 0; line < 7; line++)
	{
		if (arr[line] == *(S->esp - 1))        //将栈顶符号在arr[]中的位置作为行下标
			break;
	}
	for (row = 0; row < 7; row++)
	{
		if (arr[row] == c)      //将读取的运算符在arr[]中的位置作为列下标
			break;
	}
	return list[line][row];      //通过优先级表，返回优先级关系
}


int operation(int a, char symbol, int b)        
{
	int ret = 0;
	switch (symbol)
	{
	case '+':
		ret = a + b;
		break;
	case '-':
		ret = a - b;
		break;
	case '*':
		ret = a*b;
		break;
	case '/':
		ret = a / b;
		break;
	default:
		break;
	}
	return ret;
}


int judge_num(char c)             //判断读取的是不是数字
{
	int i = 0;
	for (i = 0; i < 7; i++)
	{
		if (arr[i] == c)                        
			break;
	}
	if (i == 7)
		return 1;            //如果是数字则返回1
	else
		return 0;                 //如果不是数字则返回0
}



#include"expression.h"
int main()
{

	stack_num num_stack;
	creatstack_num(&num_stack);               //建立一个运算数栈
	stack_operation operator_stack;
	creatstack_operation(&operator_stack);         //建立一个运算符栈
	int c;
	char symbol;
	int a = 0;
	int b = 0;
	int ret = 0;
	push_operation(&operator_stack, '#');       //将‘#’入栈，作为运算符栈的栈底
	c=getchar();
	while (c!='#'||*(operator_stack.esp-1)!='#'）     //接受表达式并且判断表达式是否输入完毕
	{	
		if (judge_num(c))            //如果是数字则进入运算数栈
		{
			int num = 0;
			while (judge_num(c))        //把连续的char类型的数字全部读取并转化成相应的整数
			{
				num = num * 10 + (c-'0');   //因为这是的运算数是char类型，所以先要转换成int
				c = getchar();
			}
			push_num(&num_stack,num);       //将运算数入栈
		}
		else                                                        
		{
			switch (judge_priority(&operator_stack,c))   //判断读取的运算符与栈顶符号的优先级关系
			{
			case '<':      //如果读取的符号优先级高，则直接进入运算符栈
				push_operation(&operator_stack, c);
				c=getchar();
				break;
			case '>':           //如果读取的符号优先级低，则栈顶符号退栈，将运算结果入栈
				pop_opreation(&operator_stack, &symbol); //则栈顶符号退栈
				pop_num(&num_stack, &b);                
				pop_num(&num_stack, &a)        // 将运算数栈栈顶的两个元素弹出
				ret=operation(a, symbol, b);  //将这两个元素进行运算
				push_num(&num_stack, ret);     //将运算结果入栈
				break;
			case '=':     //当读取到“）”时则一直退栈直到遇到“（”
				pop_opreation(&operator_stack, &symbol);
				c=getchar();
				break;
			default:
				break;
			}
		}		

	}
	printf("%d\n", *(num_stack.esp-1));     //将运算数栈最后剩下的数输出
	system("pause");
	free(num_stack.ebp);
	free(operator_stack.ebp);
	return 0;
}