資料結構（C語言）堆疊的應用——撰寫一個四則運算計算器（輸入數學公式得出計算結果）
文章目錄
- 資料結構（C語言）堆疊的應用——撰寫一個四則運算計算器（輸入數學公式得出計算結果）
- 前言
- 一、需要用到的知識點
- 1.堆疊的特點
- 2.要先明白怎么讓計算機認得你輸入的數學運算式
- 2.1解決方案——將運算式轉為后綴運算式
- 二、有了理論知識后我們開搞
- 1.準備作業
- 2.大致的實作程序
- 3.個函式實作的詳細步驟
- 3.1： int LeftPri(char op); //左運算子op的優先級和 int RightPri(char op); //右運算子op的優先級
- 3.2： bool InOp(char ch) //判斷ch是否為運算子
- 3.3：int ConpareCode(char op1, char op2); //比較op1與op2的優先級
- 3.4：void Transform(char* exp, char postExp[]); //將exp（用戶輸入的運算式）轉變成堆疊中元素，通過堆疊的特性將運算式轉換為后綴運算式并存入postExp[]中
- 3.5：float Compute(char * postExp) //進行后綴運算式運算，回傳結果
- 4. 最終效果
- 總結
- 附錄（全部的源代碼）
前言
堆疊真的很神奇當你第一次學到它的時候會覺得就這？一個結構體中定義了一個陣列，和一個整型變數指向陣列，實在是想不出它有什么作用，存盤資料用陣列和鏈表不香嗎？直到發現它在計算器中的應用才發現堆疊是永遠的神！
一、需要用到的知識點
1.堆疊的特點
定義一個堆疊
struct
{
char data[MaxSize]; //儲存資料的陣列,MaxSize是堆疊儲存最大容量
int top; //int 型別的“指標”
} op; //用top來對data中陣列的操作
2.要先明白怎么讓計算機認得你輸入的數學運算式
比如你在鍵盤上輸入(7+6×3)/(2+3)這個全部可以用字串陣列來保存，將運算子與數字分離出也不太難，正真要費點腦子的是搞清楚各種符號的優先級我們人當然知道在上述公式中6×3優先于7+6而括號中的（7+6×3）與（2+3）優先于/ 所以怎么讓計算機理解這個是本程式的最大難點，
2.1解決方案——將運算式轉為后綴運算式
同樣上述例子將其轉換為7#6#3#×+2#3+/ 用#分隔數字將運算子號后置，保存在一個堆疊中，設計一個演算法只運算前兩位將結果又儲存進堆疊 （這個堆疊就暫定義為op），就可以實作運算子號優先級運算了，
這里參考“資料結構教程”：
二、有了理論知識后我們開搞
1.準備作業
這里定義了兩個特殊的結構體陣列，左結構體陣串列示堆疊op的頂元素（op.data[op.top]）中的運算字符的優先級（簡單來說就是用先儲存進來的運算子與后儲存進來的運算子做比較）右結構體陣串列示exp（后進來的運算子）
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 30
struct
{ //設定運算子優先級
char ch; //運算子
int pri; //優先級
}leftPri[] = { {'=', 0}, {'(', 1}, {'*', 5}, {'/', 5}, {'+', 3}, {'-', 3}, {')', 6} },
rightPri[] = { {'=', 0}, {'(', 6}, {'*', 4}, {'/', 4}, {'+', 2}, {'-', 2}, {')', 1} };
//rightPri[]與leftPri[]表示運算子相同時優先級會比低的數學意義是“先左后右”
2.大致的實作程序
int LeftPri(char op); //左運算子op的優先級
int RightPri(char op); //右運算子op的優先級
bool InOp(char ch); //判斷ch是否為運算子
int ConpareCode(char op1, char op2); //比較op1與op2的優先級
void Transform(char* exp, char postExp[]); //將exp（用戶輸入的運算式）轉變成堆疊中元素，通過堆疊的特性將運算式轉換為后綴運算式并存入postExp[]中
float Compute(char* postExp); //進行后綴運算式運算，回傳結果
int main()
{
char exp[30];
printf("計算器：\n\n");
printf("請輸入數學計算公式：");
scanf("%s", exp);
char postExp[MaxSize];
Transform(exp, postExp);
printf("答案：%g\n\n", Compute(postExp));
return 0;
}
3.個函式實作的詳細步驟
3.1： int LeftPri(char op); //左運算子op的優先級和 int RightPri(char op); //右運算子op的優先級
總的來說：就是輸入一個運算子回傳與之對應的優先級數
int LeftPri(char op) //左運算子op的優先級
{
for(int i = 0; i < 7; i++) //遍歷leftPri[]陣列，找到與之對應的優先級并回傳
if (leftPri[i].ch == op)
return leftPri[i].pri;
}
int RightPri(char op) //右運算子op的優先級
{
int i;
for (int i = 0; i < 7; i++)
if (rightPri[i].ch == op)
return rightPri[i].pri;
}
3.2： bool InOp(char ch) //判斷ch是否為運算子
一個小組件函式
bool InOp(char ch) //判斷ch是否為運算子
{
if (ch == '(' || ch == ')' || ch == '+' || ch == '-' || ch == '*' || ch == '/')
return true;
else
return false;
}
3.3：int ConpareCode(char op1, char op2); //比較op1與op2的優先級
一個比較小組件函式
int ConpareCode(char op1, char op2)
{
if (LeftPri(op1) == RightPri(op2))
return 0;
else if (LeftPri(op1) < RightPri(op2))
return -1;
else
return 1;
}
3.4：void Transform(char* exp, char postExp[]); //將exp（用戶輸入的運算式）轉變成堆疊中元素，通過堆疊的特性將運算式轉換為后綴運算式并存入postExp[]中
這個函式可以算是這個程式最復雜的，一定要認真看才能看的懂
void Transform(char* exp, char postExp[])
{
struct //建立一個臨時的堆疊，
{
char data[MaxSize];
int top;
} op;
int i = 0;
int flag = 0;
op.top = -1; //令其指向空
op.top++;
op.data[op.top] = '='; //top = 0，將堆疊頂存入“=”做為結束的標語
while (*exp != '\0')
{
if (!InOp(*exp)) //將數字與運算子號分開
{
while (*exp >= '0' && *exp <= '9')
{
postExp[i++] = *exp;
exp++;
}
postExp[i++] = '#'; //在每個數字后加一個“#”將連續的數字分開
}
else
{
switch (ConpareCode(op.data[op.top], *exp)) //注意每次都跟堆疊頂比
{
case -1: //*exp中的運算子優先級高將它入堆疊
op.top++; //top = 1
op.data[op.top] = *exp;
exp++; //繼續遍歷
break;
case 0: //只有“=”和“（”才會出現這種情況，
op.top--; //top = 0 //如果先前碰到了就將原有的運算子退堆疊，可以認為將（+）中的+輸入到poseExp中
exp++;
break;
case 1:
postExp[i++] = op.data[op.top]; // 如果堆疊頂優先級高就直接輸入進postExp
op.top--;
break;
}
}
}
while (op.data[op.top] != '=') //減到0之后就退出，
{
postExp[i++] = op.data[op.top];
op.top--; //top的值越大，優先級就越高！
}
postExp[i] = '\0'; //表字串結束
}
3.5：float Compute(char * postExp) //進行后綴運算式運算，回傳結果
float Compute(char * postExp)
{
struct
{
float data[MaxSize]; //定義一個載體堆疊
int top;
} ser;
float a, b, c, d;
ser.top = -1;
while (*postExp != '\0')
{
switch (*postExp) //進行判斷運算字符
{
case '+':
a = ser.data[ser.top];
ser.top--;
b = ser.data[ser.top];
ser.top--;
c = a + b;
ser.top++;
ser.data[ser.top] = c; //將結果存入原來 b 值的位置
break;
case '-':
a = ser.data[ser.top];
ser.top--;
b = ser.data[ser.top];
ser.top--;
c = b - a;
ser.top++;
ser.data[ser.top] = c;
break;
case '*':
a = ser.data[ser.top];
ser.top--;
b = ser.data[ser.top];
ser.top--;
c = b * a;
ser.top++;
ser.data[ser.top] = c;
break;
case '/':
a = ser.data[ser.top];
ser.top--;
b = ser.data[ser.top];
ser.top--;
if (a!= 0) //除數不能為零
{
c = b / a;
ser.top++;
ser.data[ser.top] = c;
}
else
{
printf("\n\t格式錯誤");
exit(0);
}
break;
default:
d = 0;
while (*postExp >= '0' && *postExp <= '9')
{
d = 10 * d + *postExp - '0'; //將數字剝離出來
postExp++; //兩個postExp++恰好跳過了‘#’符號
}
ser.top++;
ser.data[ser.top] = d;
}
postExp++; //回圈繼續
}
return(ser.data[ser.top]); 回傳結果
}
4. 最終效果
輸入公式
輸出結果
總結
程式的基本步驟為：輸入運算式—>轉換為后綴運算式—>計算—>輸出，為實作看似簡單的數學基本運算C語言的代碼行數竟干到了200行，而其中函式幾個功能對于新手來說比較硬核，但當你搞明白了之后你就會發現支持這個計算器底層運行規律的不是代碼而是數學
萬物基于C語言（×）
萬物基于數學（√）
附錄（全部的源代碼）
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 30
struct //設定運算子優先級
{ //運算子
char ch; //優先級
int pri;
}leftPri[] = { {'=', 0}, {'(', 1}, {'*', 5}, {'/', 5}, {'+', 3}, {'-', 3}, {')', 6} },
rightPri[] = { {'=', 0}, {'(', 6}, {'*', 4}, {'/', 4}, {'+', 2}, {'-', 2}, {')', 1} };
int LeftPri(char op); //左運算子op的優先級
int RightPri(char op); //右運算子op的優先級
bool InOp(char ch); //判斷ch是否為運算子
int ConpareCode(char op1, char op2); //比較op1與op2的優先級
void Transform(char* exp, char postExp[]); //將exp（用戶輸入的運算式）轉變成堆疊中元素，
float Compute(char* postExp); //進行后綴運算式運算，回傳結果
int main()
{
char exp[30];
printf("計算器：\n\n");
printf("請輸入數學計算公式：");
scanf("%s", exp);
char postExp[MaxSize];
Transform(exp, postExp);
printf("答案：%g\n\n", Compute(postExp));
return 0;
}
int LeftPri(char op) //左運算子op的優先級
{
for(int i = 0; i < 7; i++)
if (leftPri[i].ch == op)
return leftPri[i].pri;
}
int RightPri(char op) //右運算子op的優先級
{
int i;
for (int i = 0; i < 7; i++)
if (rightPri[i].ch == op)
return rightPri[i].pri;
}
bool InOp(char ch) //判斷ch是否為運算子
{
if (ch == '(' || ch == ')' || ch == '+' || ch == '-' || ch == '*' || ch == '/')
return true;
else
return false;
}
int ConpareCode(char op1, char op2)
{
if (LeftPri(op1) == RightPri(op2))
return 0;
else if (LeftPri(op1) < RightPri(op2))
return -1;
else
return 1;
}
void Transform(char* exp, char postExp[])
{
struct
{
char data[MaxSize];
int top;
} op;
int i = 0;
int flag = 0;
op.top = -1;
op.top++;
op.data[op.top] = '='; //top = 0
while (*exp != '\0')
{
if (!InOp(*exp))
{
while (*exp >= '0' && *exp <= '9')
{
postExp[i++] = *exp;
exp++;
}
postExp[i++] = '#';
}
else
{
switch (ConpareCode(op.data[op.top], *exp)) //top = 0即op.data[op.top] = '='
{
case -1:
op.top++; //top = 1
op.data[op.top] = *exp;
exp++;
break;
case 0:
op.top--; //top = 0
exp++;
break;
case 1:
postExp[i++] = op.data[op.top];
op.top--;
break;
}
}
}
while (op.data[op.top] != '=') //減到0之后就退出，
{
postExp[i++] = op.data[op.top];
op.top--; //top的值越大，優先級就越高！
}
postExp[i] = '\0';
}
float Compute(char * postExp)
{
struct
{
float data[MaxSize];
int top;
} ser;
float a, b, c, d;
ser.top = -1;
while (*postExp != '\0')
{
switch (*postExp)
{
case '+':
a = ser.data[ser.top];
ser.top--;
b = ser.data[ser.top];
ser.top--;
c = a + b;
ser.top++;
ser.data[ser.top] = c;
break;
case '-':
a = ser.data[ser.top];
ser.top--;
b = ser.data[ser.top];
ser.top--;
c = b - a;
ser.top++;
ser.data[ser.top] = c;
break;
case '*':
a = ser.data[ser.top];
ser.top--;
b = ser.data[ser.top];
ser.top--;
c = b * a;
ser.top++;
ser.data[ser.top] = c;
break;
case '/':
a = ser.data[ser.top];
ser.top--;
b = ser.data[ser.top];
ser.top--;
if (a!= 0)
{
c = b / a;
ser.top++;
ser.data[ser.top] = c;
}
else
{
printf("\n\t格式錯誤");
exit(0);
}
break;
default:
d = 0;
while (*postExp >= '0' && *postExp <= '9')
{
d = 10 * d + *postExp - '0';
postExp++; //兩個postExp++恰好跳過了‘#’符號
}
ser.top++;
ser.data[ser.top] = d;
}
postExp++;
}
return(ser.data[ser.top]);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/246166.html
標籤：其他
上一篇：CDH環境搭建及部署
下一篇：Cisco模擬計算機網路設計：某工廠園區網有：2個分廠（分別是：零件分廠、總裝分廠）+1個總廠網路中心 + 1個總廠會議室；