運算子間的優先級關系：
鏈堆疊結構體定義：
資料域使用字串長度為20的字符陣列(故需要注意判斷讀取的字串是運算子還是數值)
可支持浮點型資料，負數， 整型資料的運算
float EvaluateExpression() 函式實作步驟：
1）初始化OPTR堆疊和OPND堆疊，將運算式起始符 “#” 壓入OPTR堆疊，
2）掃描運算式，讀入第一個字串str，如果運算式沒有掃描完畢至 "#" 或壓入OPTR的堆疊頂元素不為 "#" 時，則回圈執行以下操作：
——>使用 str_to_float() 函式判斷輸入的字串str是否是運算子
——>如果str不是運算子，則壓入OPND堆疊，讀取下一個字串str
——>如果字串str是運算子，使用 Precede() 函式獲取OPTR堆疊頂元素的運算子和字串str的運算子的優先級：
——>若是 ‘<’ ，則字串str壓入OPTR堆疊，讀入下一個字串str
——>若是 ‘>’ ，則彈出OPTR堆疊頂的運算子字串，從OPND堆疊彈出兩個數值字串，使用 Operate() 函式對兩個字串進行運算，將得到的浮點型運算結果使用 float_to_str() 函式轉換成字串型資料，壓入OPND堆疊
——>若是 ‘=’ ，則OPTR的堆疊頂元素是 "(" 且 str 是 ")" ，這時彈出OPTR堆疊頂的 "(" ，相當于括號匹配成功，然后讀入下一字串str
3)OPND堆疊頂元素記為運算式求值結果，輸出運算結果，
實作代碼(.cpp后綴檔案)
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<math.h> 5 6 #define inf float(0x3f3f3f3f) 7 #define MAXSIZE 100 8 9 char priority[7] = {'+', '-', '*', '/', '(', ')', '#'}; 10 11 char priority_relationship[7][7] = { 12 {'>', '>', '<', '<', '<', '>', '>'}, 13 {'>', '>', '<', '<', '<', '>', '>'}, 14 {'>', '>', '>', '>', '<', '>', '>'}, 15 {'>', '>', '>', '>', '<', '>', '>'}, 16 {'<', '<', '<', '<', '<', '=', ' '}, 17 {'>', '>', '>', '>', ' ', '>', '>'}, 18 {'<', '<', '<', '<', '<', ' ', '='} 19 }; // 各個運算子之間的優先級關系 20 21 int get_index(char str[]) 22 {// 獲取相應運算子的索引 23 for(int i = 0; i < 7; i++) 24 { 25 if(str[0] == priority[i]) return i; 26 } 27 printf("未找到匹配的字符\n"); 28 } 29 30 char Precede(char inside_data[], char input_data[]) 31 {// 獲取兩個運算子之間的優先級關系 32 int inside_index = get_index(inside_data); 33 int input_index = get_index(input_data); 34 35 return priority_relationship[inside_index][input_index]; 36 } 37 38 typedef struct StackNode 39 { 40 char data[MAXSIZE]; // 壓入堆疊里面的資料都是字符型，在進行運行時，記得將字符型數字轉換為浮點型數字 41 struct StackNode *next; 42 }StackNode, *LinkStack; 43 44 void InitStack(LinkStack &S) 45 {// 構造一個空堆疊S，堆疊頂指標置空 46 S = NULL; 47 } 48 49 void Push(LinkStack &S, char data[]) 50 {// 在堆疊頂插入元素data 51 StackNode *p; 52 53 p = (StackNode *)malloc(sizeof(StackNode)); // 生成新的結點 54 strcpy(p->data, data); // 將新結點的資料域置為data 55 p->next = S; // 將新結點插入堆疊頂 56 S = p; // 修改堆疊頂指標為p 57 } 58 59 char *Pop(LinkStack &S) 60 {// 洗掉S的堆疊頂元素， 用data回傳其值 61 char data[MAXSIZE]; 62 if(S == NULL) printf("錯誤！！！\n堆疊為空， 無法執行洗掉命令..."); 63 else 64 { 65 StackNode *p; 66 67 strcpy(data, S->data); // 將堆疊頂元素賦給data 68 p = S; // 用p臨時保存堆疊頂元素的空間，以備釋放 69 S = S->next; //修改堆疊頂指標 70 free(p); // 釋放原堆疊頂元素的空間 71 return data; 72 } 73 } 74 75 char *GetTop(LinkStack &S) 76 {// 獲取堆疊頂元素 77 if(S != NULL) 78 return S->data; 79 else 80 { 81 printf("錯誤！！！\n堆疊頂為空"); 82 return "0"; 83 } 84 } 85 86 float str_to_float(char *str) 87 {// 將字串資料轉換成浮點型資料 88 float num = 0; 89 int state_1 = 0; // 用于判斷是否讀取到小數點的狀態值, 0代表還沒有讀取到 90 int state_2 = 0; //用于判斷是否讀取到負號的狀態值， 0代表還沒有讀取到 91 while(( *str != '\0' && *str >= '0' && *str <= '9') || *str == '.' || (*str == '-' && *(str + 1) != '\0')) 92 {// 注意判斷小數點和負號 93 if(*str == '.') state_1 = 1; // 當讀取到小數點的時候， 狀態值state_1賦值為1 94 else if(*str == '-') state_2 = 1; // 當讀取到負號的時候， 狀態值state_2賦值為1 95 else 96 { 97 if(state_1 == 0) num = num * 10 + (*str - '0'); 98 else 99 { 100 num += (*str - '0') * pow(0.1, state_1); 101 state_1++; 102 } 103 } 104 str++; 105 } 106 if(*str != '\0') return inf; 107 else if(state_2 == 1) 108 { 109 return num * -1; 110 } 111 else return num; 112 } 113 114 char *float_to_str(float num) 115 {// 將浮點型資料裝換成字串資料，保留浮點型資料小數點后4位的值 116 char str[MAXSIZE]; 117 sprintf(str, "%.4f", num); // 保留小數點后4位 118 return str; 119 } 120 121 122 float Operate(char a[], char theta[], char b[]) 123 {//執行運算 124 float a_num = str_to_float(a); 125 float b_num = str_to_float(b); 126 127 if(theta[0] == '+') return a_num + b_num; 128 else if(theta[0] == '-') return a_num - b_num; 129 else if(theta[0] == '*') return a_num * b_num; 130 else if(theta[0] == '/') return a_num / b_num; 131 else printf("錯誤！！！\n無該運算子"); 132 } 133 134 void EvaluateExpression() 135 { 136 StackNode *OPND, *OPTR; 137 char str[MAXSIZE]; 138 char theta[MAXSIZE]; 139 char a[MAXSIZE]; 140 char b[MAXSIZE]; 141 142 InitStack(OPND); // 初始化堆疊 OPND 143 InitStack(OPTR); // 初始化堆疊 OPTR 144 Push(OPTR, "#"); // 將 "#" 壓入堆疊OPTR 145 146 printf("請輸入算術運算式（支持負數，浮點型資料），每個值用空格隔開輸入，并以#結束\n"); 147 scanf("%s", str); 148 while(str[0] != '#' || GetTop(OPTR)[0] != '#') 149 { 150 if(str_to_float(str) != inf) 151 { // 如果str不是運算子，則壓入OPND堆疊，讀取下一個字串str 152 Push(OPND, str); // 將字串str壓入OPTR堆疊 153 scanf("%s", str); // 讀入下一個字串str 154 } 155 else 156 { // 如果字串str是運算子，使用 Precede() 函式獲取OPTR堆疊頂元素的運算子和字串str的運算子的優先級 157 switch (Precede(GetTop(OPTR), str)) // 使用 Precede() 函式獲取相應優先級 158 { 159 case '<': 160 Push(OPTR, str); // 將字串str壓入OPTR堆疊 161 scanf("%s", str); // 讀入下一個字串str 162 break; 163 case '>': 164 strcpy(theta, Pop(OPTR)); // 彈出OPTR堆疊頂的運算子字串并賦值給變數 theta 165 strcpy(b, Pop(OPND)); // 彈出OPND堆疊頂的數值字串并賦值給變數 b 166 strcpy(a, Pop(OPND)); // 彈出OPND堆疊頂的數值字串并賦值給變數 a 167 char temp_str[MAXSIZE]; 168 strcpy(temp_str, float_to_str(Operate(a, theta, b))); // 根據相應的三個字串進行運算，把結果賦給temp_str 169 Push(OPND, temp_str); // 將運算結果 temp_str 壓入OPND堆疊 170 break; 171 case '=': 172 Pop(OPTR); // 彈出OPTR堆疊頂的運算子字串 173 scanf("%s", str); // 讀入下一個字串str 174 break; 175 default: 176 printf("錯誤！！！\n該優先級不存在！！！"); 177 } 178 } 179 } 180 printf("%s\n", GetTop(OPND)); 181 } 182 183 int main(void) 184 { 185 EvaluateExpression(); 186 187 system("pause"); 188 return 0; 189 }
運行結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/86642.html
標籤：C++
下一篇：遞回遍歷樹