C++代码实现逆波兰表达式

本文实例为大家分享了C++实现逆波兰表达式的具体代码，供大家参考，具体内容如下

当我们输入一个数学表达式，是中缀表达式，我们首先转换为后缀表达式（逆波兰表达式），然后再进行求值。

在《大话数据结构》的104-100页有详细的介绍，下面是我理解之后的代码实现。

代码思路：

（1）首先对输入的中缀表达式合法性进行判断，bool isStringLegal(const char* str); 函数实现。

（2）然后把中缀表达式转换为后缀表达式。

（3）根据后缀表达式求出结果，double getTheResult(vector &vec);函数实现。

注意：表达式的运算符可以输入加、减、乘、除、括号，输入的数据为整形数据，计算结果为double型数据。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
 
using namespace std;
 
#define MAX_STRING_LENGTH 100
 

string analyData(const char* str, int &i);
 

double getTheResult(vector &vec);
 

bool isCalChar(const char ch);
 

bool isStringLegal(const char* str);
 
 
 

string analyData(const char* str, int &i)
{
  int temp = i++;
  while(str[i] >= '0' && str[i] <= '9' && str[i] != '')
  {
    i++;
  }
 
  string s(str+temp,str+i);
 
  return s;
}
 

double getTheResult(vector &vec)
{
  vector::iterator it;
  stack sta;
 
  string strTemp;
  double d = 0, d1 = 0, d2 = 0;
 
  for(it = vec.begin(); it != vec.end(); it++)
  {
    strTemp = (*it);
 
    if(strTemp == "+")
    {
      d1 = sta.top();
      sta.pop();
 
      d2 = sta.top();
      sta.pop();
 
      d = d1 + d2;
      sta.push(d);
    }
    else if(strTemp == "-")
    {
      d1 = sta.top();
      sta.pop();
 
      d2 = sta.top();
      sta.pop();
 
      d = d2 - d1;
      sta.push(d);
    }
    else if(strTemp == "*")
    {
      d1 = sta.top();
      sta.pop();
 
      d2 = sta.top();
      sta.pop();
 
      d = d2 * d1;
      sta.push(d);
    }
    else if(strTemp == "/")
    {
      d1 = sta.top();
      sta.pop();
 
      d2 = sta.top();
      sta.pop();
 
      d = d2 / d1;
      sta.push(d);
    }
    else
    {
      const char *p = strTemp.c_str();
      d = atoi(p);
      sta.push(d);
    }
  }
  return sta.top();
}
 

bool isCalChar(const char ch)
{
  if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')')
  {
    return true;
  }
 
  return false;
}

bool isStringLegal(const char* str)
{
  
  if(NULL == str)
  {
    return false;
  }
 
  int len = strlen(str);
  int i = 0;
  int flag = 0;
 
  
  if(str[0] > '9' || str[0] < '0' || str[len-1] > '9' || str[len-1] < '0')
  {
    return false;
  }
 
 
  for(i = 0; str[i] != ''; i++)
  {
    
    if(isCalChar(str[i]) == false)
    {
      return false;
    }
 
    
    if(i < len-1 && isCalChar(str[i]) == true)
    {
      if(isCalChar(str[i+1]) == true)
      {
 return false;
      }
 
    }
 
    
    if(str[i] == '(')
    {
      flag++;
    }
    else if(str[i] == ')')
    {
      flag--;
    }
 
    
    if(flag < 0)
    {
      return false;
    }
  }
 
  
  if(flag != 0)
  {
    return false;
  }
 
  return true;
}
 
int main(void)
{
  char str[MAX_STRING_LENGTH] = {0};
  int i = 0;
  string data;
 
  
  stack oper_char;
 
  
  vector post_str;
 
  
  gets(str);
 
  
  if(isStringLegal(str) != true)
  {
    cout << "This expression is not legal." << endl;
  }
  else
  {
    
    for(i = 0; str[i] != ''; i++)
    {
      
      if(str[i] >= '0' && str[i] <= '9')
      {
 data = analyData(str,i);
 post_str.push_back(data);
 i--;
      }
      else if(str[i] == '(')
      {
 oper_char.push(str[i]);
      }
      else if(str[i] == ')')
      {
 char chtemp[2] = {0};
 
 chtemp[0] = oper_char.top();
 
 while(chtemp[0] != '(')
 {
   string strtemp(chtemp);
   post_str.push_back(strtemp);
   oper_char.pop();
 
   chtemp[0] = oper_char.top();
 }
 oper_char.pop();
      }
      else if(str[i] == '+' || str[i] == '-')
      {
 char chtemp[2] = {0};
 
 
 while(oper_char.size() != 0)
 {
   chtemp[0] = oper_char.top();
   if(chtemp[0] == '(')
   {
     break;
   }
 
   oper_char.pop();
 
   string strtemp(chtemp);
   post_str.push_back(strtemp);
 }
 
 
 oper_char.push(str[i]);
      }
      else if(str[i] == '*' || str[i] == '/')
      {
 char chtemp[2] = {0};
 while(oper_char.size() != 0)
 {
   chtemp[0] = oper_char.top();
   if(chtemp[0] == '(' || chtemp[0] == '+' || chtemp[0] == '-')
   {
     break;
   }
   else
   {
     oper_char.pop();
 
     string strtemp(chtemp);
     post_str.push_back(strtemp);
   }
 }
 
 
 oper_char.push(str[i]);
      }
    }
 
    
    while(!oper_char.empty())
    {
      char chtemp[2] = {0};
      chtemp[0] = oper_char.top();
      oper_char.pop();
 
      string strtemp(chtemp);
      post_str.push_back(strtemp);
    }
 
    
    cout << getTheResult(post_str) << endl;
  }
 
  return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。

C++代码实现逆波兰表达式

C/C++/C#相关栏目本月热门文章