中綴運算式轉化為后綴運算式演算法思想細節
首先明確什么是中綴運算式，什么是后綴運算式，
中綴運算式是一個通用的算識訓邏輯公式表示方法， 運算子是以中綴形式處于運算元的中間（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()函式可以用來快速判斷，讓程式終止，
- 在空間的處理上還有可以改進的方向，可以通過空間的申請釋放，考慮如何提高字串的處理長度，讓字串的處理長度達到任意值，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/163095.html
標籤：其他