表達(dá)式求值

中綴表達(dá)式：

       把運(yùn)算符放在參與運(yùn)算的兩個(gè)操作數(shù)中間的表達(dá)式稱(chēng)作中綴表達(dá)式例：“3+4*5-6/2”，因?yàn)橹芯Y表達(dá)式計(jì)算時(shí)必須按照優(yōu)先級(jí)從左向右計(jì)算，所以計(jì)算機(jī)在進(jìn)行中綴表達(dá)式求值時(shí)比較麻煩，而后綴表達(dá)式求值比較方便。

后綴表達(dá)式：

        把運(yùn)算符放在參與運(yùn)算的兩個(gè)操作數(shù)后面的表達(dá)式稱(chēng)作后綴表達(dá)式。

例：中綴表達(dá)式：3+4*5-6/2

       轉(zhuǎn)換成后綴表達(dá)式： 3  4  5 * + 6  2  /  -

        中綴表達(dá)式：9-8*（4-3）

        轉(zhuǎn)換成后綴表達(dá)式： 9   8   4  3  -  *  -

轉(zhuǎn)換規(guī)則：

        按照優(yōu)先級(jí)，把每個(gè)運(yùn)算符都移到它的兩個(gè)操作數(shù)的后面，再刪除所有的括號(hào)

后綴表達(dá)式的求值：

        從左向右一次掃描后綴表達(dá)式，遇到運(yùn)算符將將它前面的兩個(gè)運(yùn)算數(shù)取出并計(jì)算，并將結(jié)果帶入后綴表達(dá)式，直到掃描到最后一個(gè)后綴表達(dá)式。

表達(dá)式求值：

       表達(dá)式求值是棧應(yīng)用的一個(gè)基本例子，輸入一個(gè)中綴表達(dá)式，求取相應(yīng)的結(jié)果。因?yàn)橛?jì)算機(jī)不會(huì)算中綴表達(dá)式，所以我們先要將中綴表達(dá)式轉(zhuǎn)換成相應(yīng)的后綴表達(dá)式再進(jìn)行計(jì)算。要轉(zhuǎn)成相應(yīng)的后綴表達(dá)式，我們應(yīng)該創(chuàng)建兩個(gè)棧，一個(gè)用來(lái)存放操作數(shù)，一個(gè)用來(lái)存放運(yùn)算符。

中綴表達(dá)式求值的算法：

         從左向右掃描中綴表達(dá)式，若遇到操作數(shù)，則直接壓入運(yùn)算數(shù)棧，若遇到符號(hào)，則與運(yùn)算符棧的棧頂元素比較，若讀取符號(hào)的優(yōu)先級(jí)高，則讀取的符號(hào)進(jìn)棧；否則讓運(yùn)算符棧的棧頂符號(hào)退棧并且將運(yùn)算數(shù)棧最上面的兩個(gè)元素退棧，然后將運(yùn)算的結(jié)果壓入運(yùn)算數(shù)棧，一直這樣循環(huán)直到讀取的符號(hào)的優(yōu)先級(jí)高于運(yùn)算符棧頂元素。

因?yàn)槊孔x取一個(gè)符號(hào)就要與運(yùn)算符棧的棧頂元素進(jìn)行優(yōu)先級(jí)比較，我們不能每次都寫(xiě)一大堆if else語(yǔ)句，所以我們可以將運(yùn)算符的優(yōu)先級(jí)的結(jié)果放到一個(gè)二維數(shù)組中，然后利用查表法，判斷優(yōu)先級(jí)。

因?yàn)楫?dāng)我們讀取第一個(gè)符號(hào)時(shí)，運(yùn)算符棧還是個(gè)空棧，為了方便比較，我們?cè)跅５讐喝胍粋€(gè)#，并規(guī)定#的優(yōu)先級(jí)最低，并將“#”作為表達(dá)式輸入結(jié)束的標(biāo)志。

為了方便索引：我們?cè)賱?chuàng)建一個(gè)一維數(shù)組，

char arr[7] = { '+' , '-', '*', '/', '(', ')', '#' };通過(guò)它來(lái)找到棧頂符號(hào)和讀取符號(hào)在優(yōu)先級(jí)數(shù)組中的位置。

實(shí)現(xiàn)：輸入一個(gè)合法的中綴表達(dá)式，只包含“+ - * /”四種運(yùn)算符，并以“#”作為結(jié)束標(biāo)志。


//函數(shù)聲明：

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

#define STACK_INIT_MEMORY 20               //初始時(shí)開(kāi)辟棧的內(nèi)存大小
#define STACK_GROW_MEMORY 10               //當(dāng)棧滿(mǎn)時(shí)，追加內(nèi)存的大小

const char arr[7];              //聲明一個(gè)存放運(yùn)算符的一維數(shù)組，作為索引
void init_priority_list(char list[][7]);      //初始化符號(hào)表

typedef struct stack_num            //聲明一個(gè)存放運(yùn)算數(shù)的結(jié)構(gòu)體類(lèi)型
{
	int *esp;                //棧頂指針
	int *ebp;                //棧底指針
	int size;                 //記錄當(dāng)前?？臻g最多能存幾個(gè)元素
}stack_num;
void creatstack_num(stack_num *S);          //創(chuàng)建存放運(yùn)算數(shù)的棧
void push_num(stack_num *S, int x);         //將參數(shù)x中的數(shù)壓入運(yùn)算數(shù)棧中
int pop_num(stack_num *S, int *x);         //彈出棧頂元素，并通過(guò)形參x帶回

typedef struct stackpop_opreation           //聲明一個(gè)存放運(yùn)算符的結(jié)構(gòu)體類(lèi)型
{
	char *esp;                   //棧頂指針
	char *ebp;                   //棧底指針
	int size;                    //記錄當(dāng)前?？臻g最多能存幾個(gè)元素
}stack_operation;
void creatstack_operation(stack_operation *S);      //創(chuàng)建一個(gè)存放運(yùn)算符的棧
void push_operation(stack_operation *S, char symbol);  //將符號(hào)壓入運(yùn)算符棧中
int pop_opreation(stack_operation *S, char *top);    //將運(yùn)算符棧中的棧頂元素彈出




//函數(shù)實(shí)現(xiàn)：

char judge_priority(stack_operation* S, char c);       //判斷讀取的運(yùn)算符與棧頂符號(hào)的優(yōu)先級(jí),并返回
int operation(int a, char symbol, int b);          //對(duì)運(yùn)算數(shù)進(jìn)行相的運(yùn)算，并將結(jié)果返回
int judge_num(char c);          //判斷讀取的是符號(hào)還是數(shù)字，如果是數(shù)字返回1


#include"expression.h"

const char arr[7] = { '+', '-', '*', '/', '(', ')', '#' };     //通過(guò)arr[7]來(lái)查找list[][]中的優(yōu)先級(jí)

void init_priority_list(char list[][7])          //初始化優(yōu)先級(jí)列表
{
	int arr2[7] = { 1, 1, 2, 2, 3, 0, -1 };    //列作為棧頂元素，行代表讀取的運(yùn)算符
	for (int i = 0; i < 7; i++)
	{
		for (int j = 0; j < 7; j++)
		{
			if ((i == 4 && j == 5) || (i == 6 && j == 6)  //令'('與‘）’，‘#’與‘#’優(yōu)先級(jí)相同
				list[i][j] = '=';
			else
			{
				if (arr2[i] >= arr2[j])
					list[i][j] = '>';         //棧頂優(yōu)先級(jí)高
				else if (arr2[i] <= arr2[j])
					list[i][j] = '<';     //讀取的運(yùn)算符優(yōu)先級(jí)高
			}

		}
	}
}

void creatstack_num(stack_num *S)              //創(chuàng)建運(yùn)算數(shù)棧
{
	S->ebp = (int *)malloc(sizeof(int)* STACK_INIT_MEMORY);
	if (S->ebp == NULL)           //判斷動(dòng)態(tài)內(nèi)存是否開(kāi)辟成功
		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)       //判斷當(dāng)前棧是否已滿(mǎn)
	{                         //棧滿(mǎn)追加空間
		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)           //創(chuàng)建運(yùn)算符棧
{
	S->ebp = (char *)malloc(sizeof(char)*STACK_INIT_MEMORY);
	if (S->ebp == NULL)
		exit(1);                                               //判斷動(dòng)態(tài)內(nèi)存是否開(kāi)辟成功
	S->size = STACK_INIT_MEMORY;
	S->esp = S->ebp;
}
void push_operation(stack_operation *S, char symbol)
{
	if (S->esp - S->ebp >= S->size)                            //如果棧滿(mǎn)則追加空間
	{
		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)     //判斷棧頂運(yùn)算符與讀取的運(yùn)算符的優(yōu)先級(jí)
{
	char list[7][7];
	init_priority_list(list);           //初始化優(yōu)先級(jí)表
	int line = 0;                                  
	int row = 0;
	for (line = 0; line < 7; line++)
	{
		if (arr[line] == *(S->esp - 1))        //將棧頂符號(hào)在arr[]中的位置作為行下標(biāo)
			break;
	}
	for (row = 0; row < 7; row++)
	{
		if (arr[row] == c)      //將讀取的運(yùn)算符在arr[]中的位置作為列下標(biāo)
			break;
	}
	return list[line][row];      //通過(guò)優(yōu)先級(jí)表，返回優(yōu)先級(jí)關(guān)系
}


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)             //判斷讀取的是不是數(shù)字
{
	int i = 0;
	for (i = 0; i < 7; i++)
	{
		if (arr[i] == c)                        
			break;
	}
	if (i == 7)
		return 1;            //如果是數(shù)字則返回1
	else
		return 0;                 //如果不是數(shù)字則返回0
}



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

	stack_num num_stack;
	creatstack_num(&num_stack);               //建立一個(gè)運(yùn)算數(shù)棧
	stack_operation operator_stack;
	creatstack_operation(&operator_stack);         //建立一個(gè)運(yùn)算符棧
	int c;
	char symbol;
	int a = 0;
	int b = 0;
	int ret = 0;
	push_operation(&operator_stack, '#');       //將‘#’入棧，作為運(yùn)算符棧的棧底
	c=getchar();
	while (c!='#'||*(operator_stack.esp-1)!='#'）     //接受表達(dá)式并且判斷表達(dá)式是否輸入完畢
	{	
		if (judge_num(c))            //如果是數(shù)字則進(jìn)入運(yùn)算數(shù)棧
		{
			int num = 0;
			while (judge_num(c))        //把連續(xù)的char類(lèi)型的數(shù)字全部讀取并轉(zhuǎn)化成相應(yīng)的整數(shù)
			{
				num = num * 10 + (c-'0');   //因?yàn)檫@是的運(yùn)算數(shù)是char類(lèi)型，所以先要轉(zhuǎn)換成int
				c = getchar();
			}
			push_num(&num_stack,num);       //將運(yùn)算數(shù)入棧
		}
		else                                                        
		{
			switch (judge_priority(&operator_stack,c))   //判斷讀取的運(yùn)算符與棧頂符號(hào)的優(yōu)先級(jí)關(guān)系
			{
			case '<':      //如果讀取的符號(hào)優(yōu)先級(jí)高，則直接進(jìn)入運(yùn)算符棧
				push_operation(&operator_stack, c);
				c=getchar();
				break;
			case '>':           //如果讀取的符號(hào)優(yōu)先級(jí)低，則棧頂符號(hào)退棧，將運(yùn)算結(jié)果入棧
				pop_opreation(&operator_stack, &symbol); //則棧頂符號(hào)退棧
				pop_num(&num_stack, &b);                
				pop_num(&num_stack, &a)        // 將運(yùn)算數(shù)棧棧頂?shù)膬蓚€(gè)元素彈出
				ret=operation(a, symbol, b);  //將這兩個(gè)元素進(jìn)行運(yùn)算
				push_num(&num_stack, ret);     //將運(yùn)算結(jié)果入棧
				break;
			case '=':     //當(dāng)讀取到“）”時(shí)則一直退棧直到遇到“（”
				pop_opreation(&operator_stack, &symbol);
				c=getchar();
				break;
			default:
				break;
			}
		}		

	}
	printf("%d\n", *(num_stack.esp-1));     //將運(yùn)算數(shù)棧最后剩下的數(shù)輸出
	system("pause");
	free(num_stack.ebp);
	free(operator_stack.ebp);
	return 0;
}