C++詳解中綴表示式轉化為字尾表示式

中綴表示式轉化為字尾表示式演演算法思想細節
首先明確什麼是中綴表示式，什麼是字尾表示式。
中綴表示式是一個通用的算術或邏輯公式表示方法，操作符是以中綴形式處於運算元的中間（eg:3+4）。
附：中綴表示式不易被計算機處理。
字尾表示式，又稱逆波蘭式，指的是不包含括號，運運算元放在兩個運算物件的後面，所有的計算按運運算元出現的順序，嚴格從左向右進行(不再考慮運運算元的優先規則)。

轉化思想：
首先明確中綴轉化為字尾過程中，需要轉化的部分。
轉化內容分為兩個部分運算數和運運算元號。
運算數：可以分為正數和負數。也可以分為整數和小數。
運運算元號：分為六種，包括加減乘除和左右括號。
特別注意：關於數位的處理要注意正負號以及加減的判別。

括號分為左括號和右括號。左括號直接進棧但不輸出，右括號直接開始出棧，直到遇到左括號為止。
乘除運算在運算轉化裡處於高階運算的行列。在運算轉化過程中，遇到乘除運算直接進棧。
加減還是正負，This is a question！
正負的條件：字串的首字母為正負號。即str[0] = ±;或者正負號的前一個元素為(。eg:(+9)，(-9)。處理後應為：9，-9。
加減的條件：不為正負即為加減。
數位或小數點直接輸出，不影響棧內元素。

程式碼如下：

#include<ctype.h>
#include<assert.h>
using namespace std;

#define length 125

typedef struct{
	char *begin;
	char *end;
	int StackSize;
}SqStack;

void InitStack(SqStack *Q)
{
	Q->begin = new char[length];
	assert(Q->begin !=NULL);
	Q->end = Q->begin;
	Q->StackSize = length;
}

void InitStr(char str[])
{
	for(int i = 0;i < length;i++){
		str[i] = '\0';
	}
}

void PushStack(SqStack *Q,char c)
{
	*Q->end++ = c;
}

int StackLength(SqStack *Q)
{
	return (Q->end - Q->begin);
}

void PopStack(SqStack *Q,char *c)
{
	*c = *--Q->end;
}

void zhan()
{
	SqStack Q;
	InitStack(&Q);
	char str[length];
	InitStr(str);
	cin >> str;
	char c;
	for(int i = 0;str[i] != '\0';++i){ 
		if(isdigit(str[i]) || str[i]=='.') cout << str[i];
		else if(str[i] == '*' || str[i] == '/' || str[i] == '(') {if(str[i] != '(') cout << " ";PushStack(&Q,str[i]);}
		else if(str[i] == '+' || str[i] == '-'){
			if(!StackLength(&Q) && i != 0) {cout << " ";PushStack(&Q,str[i]);}
			else{
				if(i == 0) {
					if(str[i] == '-') cout << str[i];
					continue;
				}
				PopStack(&Q,&c);
				PushStack(&Q,c);
				if(c == '('){
					if(str[i-1] == '(') {if(str[i] == '-') cout << str[i];} 
					else {cout << " ";PushStack(&Q,str[i]);}
				}
				else{
					cout << " ";
					do{
						PopStack(&Q,&c);
						if(c == '(') break;
						else cout << c << " ";
					}while(StackLength(&Q) && c != '(');
					if(c == '(') PushStack(&Q,c);
					PushStack(&Q,str[i]);
				}
			}
		}
		else if(str[i] == ')')
		{
			PopStack(&Q,&c);
			if(c == '(') continue;
			do{
				cout << " " << c;
				PopStack(&Q,&c);
			}while(c != '(');
		}
	}
	if(StackLength(&Q)) cout << " ";
	while(StackLength(&Q)){
		PopStack(&Q,&c);
		cout << c;
		if(StackLength(&Q) != 0) cout << " ";
	 }
}


int main()
{
	zhan();
	return 0;
}

在這裡插入圖片描述

PTA提交屢次出錯的原因分析：

小數點未經處理。
正負號處理不當。應注意(+9)->9,(-9)->-9;
括號的處理應注意。若字串元素不為右括號，在依次彈棧過程中，應注意將左括號再次放回棧中。若字串元素為右括號，在彈出左括號時，不做處理。接著處理後續元素。

感悟：

StackLength()函數也可改為StackIsEmpty()函數。
assert()函數可以用來快速判斷，讓程式終止。
在空間的處理上還有可以改進的方向。可以通過空間的申請釋放，考慮如何提高字串的處理長度，讓字串的處理長度達到任意值。

C++詳解 中綴表示式轉化為字尾表示式

C++詳解中綴表示式轉化為字尾表示式