[cpp]
最近做一個題目，要求實現簡單的四則運算、支持括號和十六進制、浮點數等。同時能夠進行輸入合法檢查。
最近做一個題目，要求實現簡單的四則運算、支持括號和十六進制、浮點數等。同時能夠進行輸入合法檢查。 用逆波蘭式（後綴表達式）實現時主要包括以下幾個主要部分：
棧操作：包括入棧、出棧、是否為空、棧頂元素等，由於在棧操作中需要char型和float型，需要創建模板。
輸入合法檢查：包括輸入合法字符、輸入括號匹配、輸入括號匹配、輸入正確的十六進制、運算符無或連續。
提取輸入表達式：由於輸入的表達式中有浮點數或者十六進制數需要提取出來。
中綴表達式轉化為後綴表達式：輸入的表達式為中綴表達如a+b*c+(d*e+f)*g,需要將該表達式轉化為後綴表達式即abc*+de*f+g*+。
計算後綴表達式：從而得到計算結果
計算結果輸出處理：包括判斷是否為有十六進制，對含有十六進制表達式的輸出結果需要分析是否需要輸出十六進制、輸出結果是否為整數等
分別分析如下：
由於輸入的表達式中有數字、字符等，在後來的棧操作時需要的不僅是char型的，還需要float型（int型數字也可以用float處理）。所以棧操作如下：定義棧模板。並實現具體操作：
[cpp]
//自定義一個棧模板
template <class T>
class stack
{
public:
stack(){top = -1;}
T topElem();
T pop();
bool isEmpty();
void push(T _elem);
private:
T elem[g_iconstArrayMax];
int top;
};
//入棧
template <class T>
void stack<T>::push(T _elem)
{
if (top == g_iconstArrayMax - 1)
{
printf("棧滿!\n");
}
else
{
top++;
elem[top] = _elem;
}
}
//出棧
template <class T>
T stack<T>::pop()
{
if (top == -1)
{
printf("棧空!\n");
return 0;
}
else
{
T x = elem[top--];
return x;
}
}
//返回棧頂元素
template <class T>
T stack<T>::topElem()
{
if (top == -1)
{
printf("棧空!\n");
return 0;
}
else
{
return elem[top];
}
}
//是否為空
template <class T>
bool stack<T>::isEmpty()
{
if (top == -1)
{
return true;
}
else
{
return false;
}
}
//自定義一個棧模板
template <class T>
class stack
{
public:
stack(){top = -1;}
T topElem();
T pop();
bool isEmpty();
void push(T _elem);
private:
T elem[g_iconstArrayMax];
int top;
};
//入棧
template <class T>
void stack<T>::push(T _elem)
{
if (top == g_iconstArrayMax - 1)
{
printf("棧滿!\n");
}
else
{
top++;
elem[top] = _elem;
}
}
//出棧
template <class T>
T stack<T>::pop()
{
if (top == -1)
{
printf("棧空!\n");
return 0;
}
else
{
T x = elem[top--];
return x;
}
}
//返回棧頂元素
template <class T>
T stack<T>::topElem()
{
if (top == -1)
{
printf("棧空!\n");
return 0;
}
else
{
return elem[top];
}
}
//是否為空
template <class T>
bool stack<T>::isEmpty()
{
if (top == -1)
{
return true;
}
else
{
return false;
}
}
在對輸入的表達式進行分析，由於輸入的表達式中有可能喲float、十六進制，整數，於是需要對輸入的表達式進行分析，將操作數和操作符分別提取出來。並在提取的同時將char型型計算出float int和十六進制數字，並將十六進制數字轉化為int方便後來的計算。
該功能由函數實現如下，在該函數中分別將數字存儲在figure中，並將操作數用figure中的下標+1代替，結合操作符將，原表達式如1.23+0x23*2+（1.5*3-0.5）*2轉化為僅包含int型下標和操作符如1+2*3+（4*5-6）*7的存儲於dest中：
[cpp]
//把數字都拆出來，然後放進figure數組中，將原字符串復制到dest中，
//同時，數字全部用figure中對應的小標代替
void cToFig(char* dest,char* str,float* figure)
{
if (NULL == str)
{
printf("字符串為空！\n");
}
else
{
int j = 0;
int figNum= 0;//figure下標
int powNum = 1;//pow的次數
int destNum = 0;//dest的下標
int i = 0;
while(str[i]!='\0')
{
if (str[i] >= '0' && str[i] <= '9')
{
j = i+1;
int inte = 0;//整數
float fnum = 0.0;//浮點數
if (str[j] == 'x')//出現十六進制
{
j++;
while ((str[j]!= NULL)&&(!isOperator(str[j])))
{
j++;
}
//計算出十六進制
for (int k = i+2; k < j; k++)
{
if (str[k] >= '0' && str[k] <= '9')
{
inte = inte*16+(str[k]-'0');//這裡要區分是不是0-9 a-f
}
else
{
inte = inte*16+(str[k]-87);
}
}
figure[figNum] = inte;
dest[destNum] = figNum + '1';
destNum++;
figNum++;
i= j;
}
else
{
while(str[j]>='0' && str[j] <= '9')
{
j++;
}
j--;
for (int k = i; k <= j; k++)
{
inte = inte*10+str[k]-'0';
}
j++;
if (str[j] == '.')
{
powNum = 1;
i = j+1;
j = j+1;
while(str[j]>='0' && str[j] <= '9')
{
j++;
}
for (int k = i; k < j; k++)
{
float tempf = pow(0.1,powNum);
powNum++;
fnum=fnum+tempf*(str[k]-'0');
}
i = j;
figure[figNum] = inte+fnum;
dest[destNum] = figNum + '1';
destNum++;
figNum++;
}
else
{
i = j;
figure[figNum] = inte;
dest[destNum] = figNum + '1';
destNum++;
figNum++;
}
}
}
else
{
dest[destNum] = str[i];
i++;
destNum++;
}
}
dest[destNum] = '\0';
}
}
//把數字都拆出來，然後放進figure數組中，將原字符串復制到dest中，
//同時，數字全部用figure中對應的小標代替
void cToFig(char* dest,char* str,float* figure)
{
if (NULL == str)
{
printf("字符串為空！\n");
}
else
{
int j = 0;
int figNum= 0;//figure下標
int powNum = 1;//pow的次數
int destNum = 0;//dest的下標
int i = 0;
while(str[i]!='\0')
{
if (str[i] >= '0' && str[i] <= '9')
{
j = i+1;
int inte = 0;//整數
float fnum = 0.0;//浮點數
if (str[j] == 'x')//出現十六進制
{
j++;
while ((str[j]!= NULL)&&(!isOperator(str[j])))
{
j++;
}
//計算出十六進制
for (int k = i+2; k < j; k++)
{
if (str[k] >= '0' && str[k] <= '9')
{
inte = inte*16+(str[k]-'0');//這裡要區分是不是0-9 a-f
}
else
{
inte = inte*16+(str[k]-87);
}
}
figure[figNum] = inte;
dest[destNum] = figNum + '1';
destNum++;
figNum++;
i= j;
}
else
{
while(str[j]>='0' && str[j] <= '9')
{
j++;
}
j--;
for (int k = i; k <= j; k++)
{
inte = inte*10+str[k]-'0';
}
j++;
if (str[j] == '.')
{
powNum = 1;
i = j+1;
j = j+1;
while(str[j]>='0' && str[j] <= '9')
{
j++;
}
for (int k = i; k < j; k++)
{
float tempf = pow(0.1,powNum);
powNum++;
fnum=fnum+tempf*(str[k]-'0');
}
i = j;
figure[figNum] = inte+fnum;
dest[destNum] = figNum + '1';
destNum++;
figNum++;
}
else
{
i = j;
figure[figNum] = inte;
dest[destNum] = figNum + '1';
destNum++;
figNum++;
}
}
}
else
{
dest[destNum] = str[i];
i++;
destNum++;
}
}
dest[destNum] = '\0';
}
}
然後是將轉化後的僅包含int型的中綴表達式轉化為後綴表達式。中綴表達式轉化為後綴表達式需要借助棧，當遇到操作數時放入數組壓入棧，當遇到操作符時與棧頂元素進行比較，如果優先級低於棧頂元素則依次彈出，否則入棧，當遇到‘（’，直接壓棧，但是遇到‘）'，將棧內元素依次彈入到數組中直到遇到‘（’，具體實現如下：
[cpp]
void midToback(char* backStr, char* midStr,int& m)
{
if (NULL == midStr)
{
printf("表達式為空！\n");
}
else
{
stack<char> oper;
//initStack(oper);
int len = strlen(midStr);
//char operOfMid = '\0';
for (int i = 0; i < len; i++)
{
//遇見表示操作數的數組下標
if (midStr[i] >= '1')
{
backStr[m] = midStr[i];
m++;
}
else if (midStr[i] == '(')
{
oper.push(midStr[i]);
}
else if (midStr[i] == '+')
{
//operOfMid = oper.top();
while (!oper.isEmpty()&&((oper.topElem()=='-') ||(oper.topElem()=='*')||(oper.topElem()=='/')||(oper.topElem()=='+')))
{
backStr[m++] = oper.topElem();
oper.pop();
}
oper.push(midStr[i]);
}
else if (midStr[i] == '-')
{
while (!oper.isEmpty()&&((oper.topElem()=='-') ||(oper.topElem()=='*')||(oper.topElem()=='/')))
{
backStr[m++] = oper.topElem();
oper.pop();
}
oper.push(midStr[i]);
}
else if ((midStr[i] == '*')||(midStr[i] == '/'))
{
oper.push(midStr[i]);
}
else if (midStr[i] == ')')
{
while(oper.topElem()!= '(')
{
backStr[m++] = oper.topElem();
oper.pop();
}
oper.pop();
}
}
while(!oper.isEmpty())
{
backStr[m++] = oper.topElem();
oper.pop();
}
backStr[m] = '\0';
}
}
void midToback(char* backStr, char* midStr,int& m)
{
if (NULL == midStr)
{
printf("表達式為空！\n");
}
else
{
stack<char> oper;
//initStack(oper);
int len = strlen(midStr);
//char operOfMid = '\0';
for (int i = 0; i < len; i++)
{
//遇見表示操作數的數組下標
if (midStr[i] >= '1')
{
backStr[m] = midStr[i];
m++;
}
else if (midStr[i] == '(')
{
oper.push(midStr[i]);
}
else if (midStr[i] == '+')
{
//operOfMid = oper.top();
while (!oper.isEmpty()&&((oper.topElem()=='-') ||(oper.topElem()=='*')||(oper.topElem()=='/')||(oper.topElem()=='+')))
{
backStr[m++] = oper.topElem();
oper.pop();
}
oper.push(midStr[i]);
}
else if (midStr[i] == '-')
{
while (!oper.isEmpty()&&((oper.topElem()=='-') ||(oper.topElem()=='*')||(oper.topElem()=='/')))
{
backStr[m++] = oper.topElem();
oper.pop();
}
oper.push(midStr[i]);
}
else if ((midStr[i] == '*')||(midStr[i] == '/'))
{
oper.push(midStr[i]);
}
else if (midStr[i] == ')')
{
while(oper.topElem()!= '(')
{
backStr[m++] = oper.topElem();
oper.pop();
}
oper.pop();
}
}
while(!oper.isEmpty())
{
backStr[m++] = oper.topElem();
oper.pop();
}
backStr[m] = '\0';
}
}
在得到後綴表達式後，對表達式進行計算，如後綴表達式為123*+45*6-7*+，同樣借助棧操作，當遇到操作數時壓入棧，遇到操作符則依次彈出兩個棧頂元素計算（需要注意：一、計算順序，二、壓入的是下標，計算時需要將對應的操作數提取出來計算）後壓入棧，實現如下：
[cpp]
float calcu(char* backStr,int m, float* fig)
{
stack<float> sResult;//定義float棧放計算結果
float a,b,c,result = 0.0;
for (int i = 0; i< m;i++)
{
if (backStr[i]>='1')
{
//將數字對應到float中的數字，並放入棧
int tempSubscript = backStr[i]-'1';
sResult.push(fig[tempSubscript]);
}
else if(backStr[i] == '-')
{
a = sResult.pop();
b = sResult.pop();
c = b-a;
sResult.push(c);
}
else if (backStr[i] == '+')
{
a = sResult.pop();
b = sResult.pop();
c = b+a;
sResult.push(c);
}
else if (backStr[i] == '*')
{
a = sResult.pop();
b = sResult.pop();
c = b*a;
sResult.push(c);
}
else if (backStr[i] == '/')
{
a = sResult.pop();
b = sResult.pop();
c = b/a;
sResult.push(c);
}
}
result = sResult.pop();
return result;
}
float calcu(char* backStr,int m, float* fig)
{
stack<float> sResult;//定義float棧放計算結果
float a,b,c,result = 0.0;
for (int i = 0; i< m;i++)
{
if (backStr[i]>='1')
{
//將數字對應到float中的數字，並放入棧
int tempSubscript = backStr[i]-'1';
sResult.push(fig[tempSubscript]);
}
else if(backStr[i] == '-')
{
a = sResult.pop();
b = sResult.pop();
c = b-a;
sResult.push(c);
}
else if (backStr[i] == '+')
{
a = sResult.pop();
b = sResult.pop();
c = b+a;
sResult.push(c);
}
else if (backStr[i] == '*')
{
a = sResult.pop();
b = sResult.pop();
c = b*a;
sResult.push(c);
}
else if (backStr[i] == '/')
{
a = sResult.pop();
b = sResult.pop();
c = b/a;
sResult.push(c);
}
}
result = sResult.pop();
return result;
}
計算結果出來之後，需要對計算結果進行分析：首先表達式中是否有十六進制，如果有十六進制且結果為整數則需要轉化為十六進制輸出，否則就按照i整數或者小數輸出，所以這裡還需要進行判斷是否為整數，和十進制轉化為十六進制。
[cpp]
void tenToSixteen(char* sixteen,int n)
{
int shang = 0;
int yushu = 0;
int value = 1;
int i = 0;
while(value <= n)
{
value = value*16;
yushu = n % value;
shang = yushu * 16 /value;
if (shang >=0 && shang <=9)
{
sixteen[i] = (char)(shang+48);
}
else
{
sixteen[i] =(char)(shang+87);
}
i++;
}
char str[g_iconstArrayMax] = "0x";
strrev(sixteen);
strcat(str,sixteen);
strcpy(sixteen,str);
}
//判斷結果是不是int型
bool isInte(float fresult)
{
char fresultStr[g_iconstArrayMax];
sprintf(fresultStr,"%f",fresult);
if (NULL == fresultStr)
{
return false;
}
else
{
int len = strlen(fresultStr);
int i = 0;
while (fresultStr[i]!='.')
{
i++;
}
if (fresultStr[i+1] == '0')
{
return true;
}
else
{
return false;
}
}
}
void tenToSixteen(char* sixteen,int n)
{
int shang = 0;
int yushu = 0;
int value = 1;
int i = 0;
while(value <= n)
{
value = value*16;
yushu = n % value;
shang = yushu * 16 /value;
if (shang >=0 && shang <=9)
{
sixteen[i] = (char)(shang+48);
}
else
{
sixteen[i] =(char)(shang+87);
}
i++;
}
char str[g_iconstArrayMax] = "0x";
strrev(sixteen);
strcat(str,sixteen);
strcpy(sixteen,str);
}
//判斷結果是不是int型
bool isInte(float fresult)
{
char fresultStr[g_iconstArrayMax];
sprintf(fresultStr,"%f",fresult);
if (NULL == fresultStr)
{
return false;
}
else
{
int len = strlen(fresultStr);
int i = 0;
while (fresultStr[i]!='.')
{
i++;
}
if (fresultStr[i+1] == '0')
{
return true;
}
else
{
return false;
}
}
}另外關於輸入是否合法的檢查，兩個函數實現一個進行具體的判斷，另一個判斷括號是否匹配，同樣利用棧操作實現：
[cpp]
bool IsMatch(char* str)
{
//初始化棧
stack<char> s;
//initStack(s);
int len = strlen(str);
char pp[g_iconstArrayMax];
char temp;
int k = 0;
for (int i= 0; i<len;i++)
{
switch(str[i])
{
case '(':
s.push(str[i]);
break;
case')':
{
temp = s.pop();
if (temp!='(')
{
return 0;
}
else
{
pp[k] = temp;
k++;
}
break;
}
default:
break;
}
}
pp[k] = '\0';
// 判斷棧是否為空
if (s.isEmpty())
{
return true;
}
else
{
return false;
}
}
//檢測是否合法
bool isRightInput(char* str)
{
//是否輸入字符非法
if (NULL == str)
{
return false;
}
else
{
int len = strlen(str);
for (int i = 0; i<len; i++)
{
if (str[i]< '0')
{
if ((str[i] != '+')&&(str[i] != '-')&&(str[i] != '*')
&&(str[i] != '/')&&(str[i] != '.')&&(str[i] != '(')
&&(str[i] != ')'))
{
printf("輸入非法字符！\n");
return false;
}
}
else if ( str[i]> '9')
{
if ((str[i] < 'a'))
{
printf("輸入非法字符！\n");
return false;
}
else if ((str[i] > 'f')&&(str[i] != 'x'))
{
printf("輸入非法字符！\n");
return false;
}
else if(str[i] == 'x')
{
if (str[i-1] != '0')
{
printf("輸入十六進制非法，請以0x開頭！\n");
return false;
}
}
else
{
if (str[i-1]!='x')
{
printf("輸入非法字符！\n");
return false;
}
}
}
}
//檢測括號匹配
if (!IsMatch(str))
{
printf("括號不匹配！\n");
return false;
}
//檢測是否出現連續的運算符或者沒有運算法
int num = 0;
int k = 0;
for (int j = 0; j< len; j++)
{
if ((str[j] == '+')||(str[j] == '-')||(str[j] == '*')
||(str[j] == '/'))
{
num++;
k = j;
if ((str[k-1] == '+')||(str[k-1] == '-')||(str[k-1] == '*')
||(str[k-1] == '/')||(str[k+1] == '+')||(str[k+1] == '-')||(str[k+1] == '*')
||(str[k+1] == '/'))
{
printf("出現連續運算符！\n");
return false;
}
else if ((str[j] == '/')&&(str[k+1] == '0'))
{
printf("被除數不能為0！\n");
return false;
}
else if (str[k+1] == NULL)
{
printf("輸入不完整！\n");
return false;
}
}
}
if (num == 0)
{
printf("無運算符！\n");
return false;
}
return true;
}
}
bool IsMatch(char* str)
{
//初始化棧
stack<char> s;
//initStack(s);
int len = strlen(str);
char pp[g_iconstArrayMax];
char temp;
int k = 0;
for (int i= 0; i<len;i++)
{
switch(str[i])
{
case '(':
s.push(str[i]);
break;
case')':
{
temp = s.pop();
if (temp!='(')
{
return 0;
}
else
{
pp[k] = temp;
k++;
}
break;
}
default:
break;
}
}
pp[k] = '\0';
// 判斷棧是否為空
if (s.isEmpty())
{
return true;
}
else
{
return false;
}
}
//檢測是否合法
bool isRightInput(char* str)
{
//是否輸入字符非法
if (NULL == str)
{
return false;
}
else
{
int len = strlen(str);
for (int i = 0; i<len; i++)
{
if (str[i]< '0')
{
if ((str[i] != '+')&&(str[i] != '-')&&(str[i] != '*')
&&(str[i] != '/')&&(str[i] != '.')&&(str[i] != '(')
&&(str[i] != ')'))
{
printf("輸入非法字符！\n");
return false;
}
}
else if ( str[i]> '9')
{
if ((str[i] < 'a'))
{
printf("輸入非法字符！\n");
return false;
}
else if ((str[i] > 'f')&&(str[i] != 'x'))
{
printf("輸入非法字符！\n");
return false;
}
else if(str[i] == 'x')
{
if (str[i-1] != '0')
{
printf("輸入十六進制非法，請以0x開頭！\n");
return false;
}
}
else
{
if (str[i-1]!='x')
{
printf("輸入非法字符！\n");
return false;
}
}
}
}
//檢測括號匹配
if (!IsMatch(str))
{
printf("括號不匹配！\n");
return false;
}
//檢測是否出現連續的運算符或者沒有運算法
int num = 0;
int k = 0;
for (int j = 0; j< len; j++)
{
if ((str[j] == '+')||(str[j] == '-')||(str[j] == '*')
||(str[j] == '/'))
{
num++;
k = j;
if ((str[k-1] == '+')||(str[k-1] == '-')||(str[k-1] == '*')
||(str[k-1] == '/')||(str[k+1] == '+')||(str[k+1] == '-')||(str[k+1] == '*')
||(str[k+1] == '/'))
{
printf("出現連續運算符！\n");
return false;
}
else if ((str[j] == '/')&&(str[k+1] == '0'))
{
printf("被除數不能為0！\n");
return false;
}
else if (str[k+1] == NULL)
{
printf("輸入不完整！\n");
return false;
}
}
}
if (num == 0)
{
printf("無運算符！\n");
return false;
}
return true;
}
}
實現結果如下：
