浮点数四则运算小程序利用符号优先级和双栈

本文主要是介绍浮点数四则运算小程序利用符号优先级和双栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

来源：http://www.cnblogs.com/xieduo/articles/776665.html

浮点数四则运算小程序利用符号优先级和双栈

/**************四则运算*************/
/***********作者：xiaocui**********/
/***********时间：2006.10.27*******/
/***********版本：v1.0*************/

/*******解决方案：按照编译原理里面的算符优先
算法，定义算符＋－ * / ( ) 的优先级；设置两个
栈：符号栈和数字栈，根据优先级进行压栈和出栈
操作，最后如果符号栈为空，则表达式正确，输出结果；
如果符号栈不空或数字栈元素超过1，则表达式错误.**/

#include
#include
#include
#include
using namespace std;

/*******定义优先级**********/
/**
+ - * / ( ) (进栈符号)
(栈顶符号)
+ > > < < < >

- > > < < < >

* > > > > < >

/ > > > > < >

( < < < < < <

) > > > > > >

***************************/
/******* > < 表示栈顶符号和要进栈符号的优先关系，
如果栈顶符号的优先级>要进栈符号的优先级，执行计算；
如果栈顶符号的优先级 <要进栈符号的优先级，符号进栈***>

/*******返回栈顶符号是否优先与进栈符号*******/
bool is_prior_exe(char top, char in)
{
if(top==')') //右括号，栈顶优先级大
{
return true;
}
if(top=='(')    //左括号，栈顶优先级小
{
return false;
}
if(top=='*' || top=='/')
{
if(in!='(')
{
   return true;
}
else
{
   return false;
}
}
if(top=='+' || top=='-')
{
if(in=='+' || in=='-' || in==')')
{
   return true;
}
if(in=='*' || in=='/' || in=='(')
{
   return false;
}
}
}

/*********把字符串转化成双精度浮点数*******/
double change_str_to_double(char *str)
{
//得到整数部分
int num=0;
while(*str!='/0' && *str!='.')
{
num=num*10+(*str-'0');
str++;
}
if(*str=='/0')
{
return num;
}
//得到小数部分
while(*str!='/0')
{
str++;
}
str--;
double num2=0;
while(*str!='.')
{
num2=num2*0.1+(*str-'0');
str--;
}
num2=num2*0.1;
return num+num2;
}

/**********简单的词法分析*********/
vector get_word(string str)
{
vector word; //装载词法分析的单词
int i=0;
while(i
{
if(str[i]=='(' || str[i]==')' || str[i]=='*' ||
     str[i]=='/' || str[i]=='+' || str[i]=='-')
{
   //运算符，构成单个单词，加入word中
   char * tmp =new char[2];
   tmp[0]=str[i];
   tmp[1]='/0';
   word.push_back(tmp);
}
if((str[i]-'0'>=0 && str[i]-'0'<=9)||str[i]=='.')
{
   static int j=-1;
   static char * tmp;
      if(j==-1) //只在第1次，建立数组保存浮点数
   {
    j=i;
    tmp=new char [15];
   }
      tmp[i-j]=str[i];
   if(i+1 9) && str[i+1]!='.')//下一个不是数字，结束字符串
   {
    tmp[i+1-j]='/0';
    word.push_back(tmp);
    j=-1;
   }
   else if (i+1==str.size()) //字符串最后一个字符是数字
   {
    tmp[i+1-j]='/0';
    word.push_back(tmp);
    j=-1;
   }
}
i++;
}
return word;
}

/******************进栈和计算处理******************/
double instack_compute (vector cpvec)
{
//建立数字栈
stack dstack;
//建立符号栈
    stack cstack;
int i=0;
while(i
{
//是数字，进数字栈
if(cpvec[i][0]-'0'>=0 && cpvec[i][0]-'0'<=9)
{
   //转化为double
   double tmp=change_str_to_double(cpvec[i]);
   dstack.push(tmp);
}
//是运算符，比较优先级决定进栈还是计算
if(cpvec[i][0]=='+' || cpvec[i][0]=='-' || cpvec[i][0]=='*' ||
     cpvec[i][0]=='/' || cpvec[i][0]=='(' || cpvec[i][0]==')' )
{
   char c_in=cpvec[i][0]; //要进栈的符号
   //符号栈为空，当前符号进栈
   if(cstack.empty())
   {
    cstack.push(c_in);
   }
   else
   {
    char c_top=cstack.top(); //栈顶符号
    if( is_prior_exe(c_top, c_in)==false)
    {
     //栈顶符号优先级低
     cstack.push(c_in);
    }
    if( is_prior_exe(c_top, c_in)==true )
    {
     //栈顶符号优先级高，开始计算
     if(c_top=='+')
     {
      double num_second=dstack.top();
      dstack.pop();
      double num_first=dstack.top();
      dstack.pop();
      double rs=num_first+num_second;
      dstack.push(rs);
      cstack.pop();
     }
     if(c_top=='-')
     {
      double num_second=dstack.top();
      dstack.pop();
      double num_first=dstack.top();
      dstack.pop();
      double rs=num_first-num_second;
      dstack.push(rs);
      cstack.pop();
     }
     if(c_top=='*')
     {
      double num_second=dstack.top();
      dstack.pop();
      double num_first=dstack.top();
      dstack.pop();
      double rs=num_first*num_second;
      dstack.push(rs);
      cstack.pop();
     }
     if(c_top=='/')
     {
      double num_second=dstack.top();
      dstack.pop();
      double num_first=dstack.top();
      dstack.pop();
      if(num_second!=0)
      {
       double rs=num_first/num_second;
       dstack.push(rs);
       cstack.pop();
      }
      else
      {
       cout<<"算术表达式中出现除数为0的错误，请检查!"<
       exit(0);
      }
     }
     if(c_top==')')
     {
      cstack.pop();
      cstack.pop();
     }
     i--; //刚才那个还在外面等的算符不能漏掉
    }
   }
}
i++; //更新循环变量 (这个怎么老是忘呢?)
}
    while(cstack.empty()!=true) //当符号栈不空，而计算式已经遍历完，开始计算
{
char c_top=cstack.top();
if(c_top=='+')
{
   double num_second=dstack.top();
   dstack.pop();
   double num_first=dstack.top();
   dstack.pop();
   double rs=num_first+num_second;
   dstack.push(rs);
   cstack.pop();
}
if(c_top=='-')
{
   double num_second=dstack.top();
   dstack.pop();
   double num_first=dstack.top();
   dstack.pop();
   double rs=num_first-num_second;
   dstack.push(rs);
   cstack.pop();
}
if(c_top=='*')
{
   double num_second=dstack.top();
   dstack.pop();
   double num_first=dstack.top();
   dstack.pop();
   double rs=num_first*num_second;
   dstack.push(rs);
   cstack.pop();
}
if(c_top=='/')
{
   double num_second=dstack.top();
   dstack.pop();
   double num_first=dstack.top();
   dstack.pop();
   if(num_second!=0)
   {
    double rs=num_first/num_second;
    dstack.push(rs);
    cstack.pop();
   }
   else
   {
    cout<<"算术表达式中出现除数为0的错误，请检查!"<
    exit(0);
   }
}
if(c_top==')')
{
   cstack.pop();
   if(cstack.empty() || cstack.top()!='(')//栈空或另外一个不是'('
   {
    cout<<"表达式有误，括号不匹配"<
    return -1;
   }
   cstack.pop();
}
}
return dstack.top();
}