棧的應用：四則運算表達式求值

棧的一個應用是求四則運算表達式的值，這裡的表達式包含數字、加減乘除4種運算符，以及小括号。

由于輸入是一個字元串，是以解決這個問題需要以下3個步驟：

1、輸入字元串轉化為中綴表達式；

2、中綴表達式轉化為字尾表達式；

3、字尾表達式求值。

現在表達式為：9 + （ 3 - 1 ）* 3 + 10 / 2 ，先看一下運作結果：

棧的應用：四則運算表達式求值

首先解釋一下中綴表達式和字尾表達式的概念。所謂中綴表達式，就是我們平常書寫的表達式，因為運算符是寫在兩個參與運算的數字中間，是以叫中綴表達式，例如1 + 2 。與此對應，字尾表達式就是運算符寫在數字後面，比如剛才的算式就要寫成1 2 + ，我們看起來的确有點奇怪，不過計算機卻很喜歡這種表達式。下面分析解決問題的3個步驟。

1、輸入字元串轉化為中綴表達式

運算符号和括号好辦，本身就是字元，隻需要把字元串形式的數字轉成相應的整數。我采用的方法是，用一個數組num[]存儲整數的各位數字，用一個整型變量count記錄位數。當下一個字元是運算符或者括号時，表示整數已經讀取完畢。這時候，把num數組的各位數字乘以10的某次方就可還原出該整數。該部分代碼如下：

//字元串轉換成中綴表達式
void StringToMidExp(const char exp[], Stack *ps)
{
	int num[MAX_INT];
	int k, n, count, temp;
	Stack m_stack;
	Stack *pm;
	Node *q;

	k = 0;
	count = 0;
	pm = &m_stack;
	InitStack(pm);

	while (exp[k] != '\0')
	{
		if (exp[k] >= '0' && exp[k] <= '9') //數字0到9
		{
			count++;					//count記錄整數的位數
			num[count-1] = exp[k] - 48;	//num數組記錄整數的每一位
		}
		else if ((exp[k] >= 40 && exp[k] <= 43) || exp[k] == 45 || exp[k] == 47) //運算符
		{
			if (count > 0) //轉換該運算符之前的數字
			{
				n = 0;
				temp = 0;
				while (n < count)
				{
					temp += num[n] * TenPow(count - n -1); //每一位乘以10的某次方
					n++;
				}				
				q = (Node *)malloc(sizeof(Node));
				q->type = NUM;
				q->number = temp;
				Push(pm, q);
			}
			count = 0; //位數清零
			q = (Node *)malloc(sizeof(Node));
			q->type = OP;
			q->operation = exp[k];
			Push(pm, q);
		}
		k++;
	}
	if (count > 0) //把最後一個數字轉換出來
	{
		n = 0;
		temp = 0;
		while (n < count)
		{
			temp += num[n] * TenPow(count - n -1);
			n++;
		}
		q = (Node *)malloc(sizeof(Node));
		q->type = NUM;
		q->number = temp;
		Push(pm, q);
	}
	Reverse(pm, ps); //颠倒一下次序
}

//計算10的n次方
int TenPow(int n)
{
	if (n == 0)
	{
		return 1;
	} 
	else
	{
		int i, k;
		i = 0;
		k = 1;
		while (i < n)
		{
			k *= 10;
			i++;
		}
		return k;
	}
}

2、中綴表達式轉字尾表達式

這裡需要一個棧用來暫時存儲運算符和括号，具體地，對中綴表達式從左到右按以下規則操作：

（1）遇到數字，則直接輸出；

（2）遇到左括号，則左括号進棧；

（3）遇到右括号，從棧頂開始依次輸出所有運算符，直到遇到左括号，這個左括号也出棧；

（4）遇到加号或減号，從棧頂開始依次輸出所有運算符，直到遇到左括号，但此時這個左括号不出棧，并且目前運算符進棧；

（5）遇到乘号或除号，如果棧頂是乘号或除号，則輸出，否則不輸出，并且目前運算符進棧。

這部分代碼如下：

//中綴表達式轉換成字尾表達式
void MidExpToBackExp(Stack *pm, Stack *pb)
{
	Stack tempStack, oprStack;
	Stack *pt, *pr;
	Node *q, *r;

	pt = &tempStack;	//臨時存儲字尾表達式
	pr = &oprStack;		//用來決定運算符的順序
	InitStack(pt);
	InitStack(pr);

	while (pm->top)
	{
		q = (Node *)malloc(sizeof(Node));
		Pop(pm, q);
		if (q->type == NUM)
		{
			Push(pt, q);
		} 
		else
		{
			if (q->operation == '+' || q->operation == '-')
			{
				while (pr->top && pr->top->operation != '(')
				{
					r = (Node *)malloc(sizeof(Node));
					Pop(pr, r);
					Push(pt, r);
				}
				Push(pr, q);
			}
			else if (q->operation == '*' || q->operation == '/')
			{
				while (pr->top && pr->top->operation != '(' && pr->top->operation != '+' && pr->top->operation != '-')
				{
					r = (Node *)malloc(sizeof(Node));
					Pop(pr, r);
					Push(pt, r);
				}
				Push(pr, q);
			}
			else if (q->operation == '(')
			{
				Push(pr, q);
			} 
			else
			{
				while (pr->top)
				{
					if (pr->top->operation == '(')
					{
						r = (Node *)malloc(sizeof(Node));
						Pop(pr, r);
						free(r);
						break;
					}
					r = (Node *)malloc(sizeof(Node));
					Pop(pr, r);
					Push(pt, r);
				}
				free(q);
			}
		}
	}
	while (pr->top) //棧内剩餘運算符全部出棧
	{
		r = (Node *)malloc(sizeof(Node));
		Pop(pr, r);
		Push(pt, r);
	}
	Reverse(pt, pb); //颠倒一下次序
}

3、字尾表達式求值

這裡還需要一個棧，隻不過這回是用來暫時存儲數字，注意到字尾表達式中不含有括号了。具體地，對字尾表達式從左到右按以下規則操作：

（1）遇到數字，則數字進棧；

（2）遇到運算符，則棧頂數字出棧，記為num1，此時棧頂數字再出棧，記為num2，那麼記num2 運算 num1 = num3，将num3進棧。還是舉個例子好了，比如遇到運算符+，棧頂數字是1，好了，1出棧。現在棧頂數字變為2了，好，2也出棧。現在計算2+1=3，此時，3進棧。

這部分代碼如下：

//根據字尾表達式計算結果
int BackExpToResult(Stack *ps)
{
	if (!ps->top) //空棧說明表達式有誤
	{
		return NO_RESULT;
	}

	Stack tempStack;
	Stack *pt;
	Node *q;
	int num_left, num_right, result;

	pt = &tempStack;
	InitStack(pt);
	while (ps->top)
	{
		if (ps->top->type == NUM)
		{
			q = (Node *)malloc(sizeof(Node));
			Pop(ps, q);
			Push(pt, q);
		} 
		else
		{
			q = (Node *)malloc(sizeof(Node));
			Pop(pt, q);
			num_right = q->number;
			free(q);

			if (!pt->top) //pt棧内沒有第2個數了，說明表達式有誤
			{
				return NO_RESULT;
			}

			q = (Node *)malloc(sizeof(Node));
			Pop(pt, q);
			num_left = q->number;
			free(q);

			q = (Node *)malloc(sizeof(Node));
			Pop(ps, q);
			switch(q->operation)
			{
			case '+':
				result = num_left + num_right;
				break;
			case '-':
				result = num_left - num_right;
				break;
			case '*':
				result = num_left * num_right;
				break;
			case '/':
				result = num_left / num_right;
				break;				
			}
			free(q);

			q = (Node *)malloc(sizeof(Node));
			q->type = NUM;
			q->number = result;
			Push(pt, q);
		}
	}
	q = (Node *)malloc(sizeof(Node));
	Pop(pt, q);
	result = q->number;
	free(q);

	if (pt->top) //pt棧内還有數字，說明表達式有誤
	{
		return NO_RESULT;
	} 
	else
	{
		return result;
	}
}

整個工作完成，不過，程式要想正确運作，對輸入有一些要求，比如：

（1）輸入不能有空字元；

（2）輸入的數字隻能是整數，而且除數不能是0；

（3）確定中間的運算結果也都是整數，否則會舍棄小數部分，進而影響精度。

全部代碼如下：

#include <STDIO.H>
#include <STDLIB.H>

#define MAX_EXP 100			//表達式最大長度
#define MAX_INT 10			//整數最大位數
#define NO_RESULT -99999	//計算異常的傳回值

enum node_type{ NUM, OP };

struct node{
	int number;
	char operation;
	enum node_type type;
	struct node *next;
};

struct stack{
	struct node *top;
	int length;
};

typedef struct node Node;
typedef struct stack Stack;

int GetResult(const char []);
void StringToMidExp(const char [], Stack *);
int TenPow(int);
void MidExpToBackExp(Stack *, Stack *);
int BackExpToResult(Stack *);
void ShowStack(const Stack *);
void ShowNode(const Node *);
void InitStack(Stack *);
void Push(Stack *, Node *);
void Pop(Stack *, Node *);
void ClearStack(Stack *);
void Reverse(Stack *, Stack *);

int main(void)
{
	char expression[MAX_EXP];
	int result;

	printf("輸入四則運算表達式：\n");
	scanf("%s", expression);

	result = GetResult(expression);
	if (result == NO_RESULT)
	{
		printf("表達式有誤，計算失敗。\n");
	} 
	else
	{
		printf("計算結果是：%d\n", result);
	}

	return 0;
}

//根據表達式的字元串計算結果
int GetResult(const char exp[])
{
	Stack middleExp, backExp;
	Stack *pm, *pb;

	pm = &middleExp;
	pb = &backExp;
	InitStack(pm);
	InitStack(pb);
	StringToMidExp(exp, pm);
	printf("中綴表達式：");
	ShowStack(pm);
	MidExpToBackExp(pm, pb);
	printf("字尾表達式：");
	ShowStack(pb);

	return BackExpToResult(pb);
}

//字元串轉換成中綴表達式
void StringToMidExp(const char exp[], Stack *ps)
{
	int num[MAX_INT];
	int k, n, count, temp;
	Stack m_stack;
	Stack *pm;
	Node *q;

	k = 0;
	count = 0;
	pm = &m_stack;
	InitStack(pm);

	while (exp[k] != '\0')
	{
		if (exp[k] >= '0' && exp[k] <= '9') //數字0到9
		{
			count++;					//count記錄整數的位數
			num[count-1] = exp[k] - 48;	//num數組記錄整數的每一位
		}
		else if ((exp[k] >= 40 && exp[k] <= 43) || exp[k] == 45 || exp[k] == 47) //運算符
		{
			if (count > 0) //轉換該運算符之前的數字
			{
				n = 0;
				temp = 0;
				while (n < count)
				{
					temp += num[n] * TenPow(count - n -1); //每一位乘以10的某次方
					n++;
				}				
				q = (Node *)malloc(sizeof(Node));
				q->type = NUM;
				q->number = temp;
				Push(pm, q);
			}
			count = 0; //位數清零
			q = (Node *)malloc(sizeof(Node));
			q->type = OP;
			q->operation = exp[k];
			Push(pm, q);
		}
		k++;
	}
	if (count > 0) //把最後一個數字轉換出來
	{
		n = 0;
		temp = 0;
		while (n < count)
		{
			temp += num[n] * TenPow(count - n -1);
			n++;
		}
		q = (Node *)malloc(sizeof(Node));
		q->type = NUM;
		q->number = temp;
		Push(pm, q);
	}
	Reverse(pm, ps); //颠倒一下次序
}

//計算10的n次方
int TenPow(int n)
{
	if (n == 0)
	{
		return 1;
	} 
	else
	{
		int i, k;
		i = 0;
		k = 1;
		while (i < n)
		{
			k *= 10;
			i++;
		}
		return k;
	}
}

//中綴表達式轉換成字尾表達式
void MidExpToBackExp(Stack *pm, Stack *pb)
{
	Stack tempStack, oprStack;
	Stack *pt, *pr;
	Node *q, *r;

	pt = &tempStack;	//臨時存儲字尾表達式
	pr = &oprStack;		//用來決定運算符的順序
	InitStack(pt);
	InitStack(pr);

	while (pm->top)
	{
		q = (Node *)malloc(sizeof(Node));
		Pop(pm, q);
		if (q->type == NUM)
		{
			Push(pt, q);
		} 
		else
		{
			if (q->operation == '+' || q->operation == '-')
			{
				while (pr->top && pr->top->operation != '(')
				{
					r = (Node *)malloc(sizeof(Node));
					Pop(pr, r);
					Push(pt, r);
				}
				Push(pr, q);
			}
			else if (q->operation == '*' || q->operation == '/')
			{
				while (pr->top && pr->top->operation != '(' && pr->top->operation != '+' && pr->top->operation != '-')
				{
					r = (Node *)malloc(sizeof(Node));
					Pop(pr, r);
					Push(pt, r);
				}
				Push(pr, q);
			}
			else if (q->operation == '(')
			{
				Push(pr, q);
			} 
			else
			{
				while (pr->top)
				{
					if (pr->top->operation == '(')
					{
						r = (Node *)malloc(sizeof(Node));
						Pop(pr, r);
						free(r);
						break;
					}
					r = (Node *)malloc(sizeof(Node));
					Pop(pr, r);
					Push(pt, r);
				}
				free(q);
			}
		}
	}
	while (pr->top) //棧内剩餘運算符全部出棧
	{
		r = (Node *)malloc(sizeof(Node));
		Pop(pr, r);
		Push(pt, r);
	}
	Reverse(pt, pb); //颠倒一下次序
}

//根據字尾表達式計算結果
int BackExpToResult(Stack *ps)
{
	if (!ps->top) //空棧說明表達式有誤
	{
		return NO_RESULT;
	}

	Stack tempStack;
	Stack *pt;
	Node *q;
	int num_left, num_right, result;

	pt = &tempStack;
	InitStack(pt);
	while (ps->top)
	{
		if (ps->top->type == NUM)
		{
			q = (Node *)malloc(sizeof(Node));
			Pop(ps, q);
			Push(pt, q);
		} 
		else
		{
			q = (Node *)malloc(sizeof(Node));
			Pop(pt, q);
			num_right = q->number;
			free(q);

			if (!pt->top) //pt棧内沒有第2個數了，說明表達式有誤
			{
				return NO_RESULT;
			}

			q = (Node *)malloc(sizeof(Node));
			Pop(pt, q);
			num_left = q->number;
			free(q);

			q = (Node *)malloc(sizeof(Node));
			Pop(ps, q);
			switch(q->operation)
			{
			case '+':
				result = num_left + num_right;
				break;
			case '-':
				result = num_left - num_right;
				break;
			case '*':
				result = num_left * num_right;
				break;
			case '/':
				result = num_left / num_right;
				break;				
			}
			free(q);

			q = (Node *)malloc(sizeof(Node));
			q->type = NUM;
			q->number = result;
			Push(pt, q);
		}
	}
	q = (Node *)malloc(sizeof(Node));
	Pop(pt, q);
	result = q->number;
	free(q);

	if (pt->top) //pt棧内還有數字，說明表達式有誤
	{
		return NO_RESULT;
	} 
	else
	{
		return result;
	}
}

//顯示棧中元素
void ShowStack(const Stack *ps)
{
	if (ps->top)
	{
		Node *p = ps->top;
		while (p->next)
		{
			ShowNode(p);
			printf(" ");
			p = p->next;
		}
		ShowNode(p);
		printf("\n");
	} 
	else
	{
		printf("無\n");
	}
}

//顯示一個節點元素
void ShowNode(const Node *p)
{
	if (p->type == NUM)
	{
		printf("%d", p->number);
	} 
	else
	{
		printf("%c", p->operation);
	}
}

//初始化棧
void InitStack(Stack *ps)
{
	ps->length = 0;
	ps->top = NULL;
}

//節點入棧
void Push(Stack *ps, Node *pn)
{
	pn->next = ps->top;
	ps->top = pn;
	ps->length++;
}

//節點出棧
void Pop(Stack *ps, Node *pn)
{
	if (ps->top)
	{
		Node *q = ps->top;
		pn->next = NULL;
		pn->number = q->number;
		pn->operation = q->operation;
		pn->type = q->type;
		ps->top = q->next;
		free(q);
		ps->length--;
	} 
	else
	{
		pn = NULL;
	}
}

//清空棧
void ClearStack(Stack *ps)
{
	Node *q;

	while (ps->top)
	{
		q = ps->top;
		ps->top = q->next;
		free(q);
		ps->length--;
	}
}

//反轉棧中元素的次序
void Reverse(Stack *ps1, Stack *ps2)
{
	if (ps1->top)
	{
		Node *q;

		ClearStack(ps2);
		while (ps1->top)
		{
			q = (Node *)malloc(sizeof(Node));
			Pop(ps1, q);
			Push(ps2, q);
		}
	} 
	else
	{
		ps2->top = NULL;
		ps2->length = 0;
	}
}

棧的應用：四則運算表達式求值

繼續閱讀

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

浮點數計算精度控制

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

C++ 第十五周報告1--《冒泡法排序》

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

回溯法迷宮求解

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

QR碼編碼原理三（日本漢字和中文編碼）

Linux裝置模型（中）之上層容器