逆波蘭式實現四則運算表達式計算器支持括號、十六進制

[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;
 }
}
實現結果如下：