如何用栈完成表达式计算?
///////////////////////////////
///表达式计算
////数据结构:栈
////作者:ZZJ_4Ever
///////////////////////////////
#include<iostream>
#include<stack>
#include<string>
#include<assert.h>
usingnamespacestd;
stack<double>data_stack;
stack<char>char_stack;
intPRI(char&ch)
{
if(ch==')'){return1;}
elseif(ch=='+'||ch=='-'){return2;}
elseif(ch=='*'||ch=='/'){return3;}
elsereturn0;
}
/*
2.扫描到操作符,与操作符栈的顶端操作符进行比较,
如果优先级小或相等,则弹出数据和操作符进行计算,将结果送入数据栈;
如果优先级较大,则进操作符栈;
如果是’(‘直接进栈,如果是’)’,遇到’(‘则抵消.
*/
voidExc_stack()
{
doubleresult_temp;
assert(char_stack.size()>=1&&data_stack.size()>=1);
doubletemp1=data_stack.top();
data_stack.pop();
doubletemp2=data_stack.top();
data_stack.pop();
charpopchar=char_stack.top();
char_stack.pop();
if(popchar=='+')
result_temp=temp2+temp1;
elseif(popchar=='-')
result_temp=temp2-temp1;
elseif(popchar=='*')
result_temp=temp2*temp1;
elseif(popchar=='/')
result_temp=temp2/temp1;
data_stack.push(result_temp);
}
voidpush_charinto(char&ch)
{
if(ch=='(')//如果是’(‘直接进栈
char_stack.push(ch);
elseif(char_stack.empty())
{
char_stack.push(ch);
}
elseif(PRI(ch)>PRI(char_stack.top()))//如果优先级较大,则进操作符栈
{
char_stack.push(ch);
}
//扫描到操作符
else//如果优先级小或相等,则弹出数据和操作符进行计算,将结果送入数据栈
{
Exc_stack();
if(ch==')')//如果是’)’,遇’(‘直接弹出.
{
while(char_stack.top()!='(')//操作括号内的内容直到遇到'('为止
{
Exc_stack();
}
char_stack.pop();
}
else
//将自己压入栈
char_stack.push(ch);
}
}
voidpush_datainto(double&db)
{
data_stack.push(db);
}
voidmain()
{
stringstr;
while(1)
{
boolflag=false;
doubleret=0.0;
doublen;
cout<<"在此输入表达式:";
//读入
cin>>str;
//处理
//筛选
////////////////////////
/////开始扫描
///////////////////////
for(inti=0;i<str.length();i++)
{
if(str[i]>='0'&&str[i]<='9')
{
if(!flag)
ret=ret*10+str[i]-'0';
else
{
ret=ret+(str[i]-'0')/n;
n*=10;
}
}
elseif(str[i]=='.')
{
n=10;
flag=true;
}
else
{
if(ret!=0||str[i-1]=='0')
push_datainto(ret);
ret=0.0;
flag=false;
push_charinto(str[i]);
}
}
//如果最后一个数字还没有压入栈
if(ret!=0||str[i-1]=='0')push_datainto(ret);
//3.扫描数据完成后,依次退栈并进行计算
assert(!data_stack.empty()||!char_stack.empty());
while(data_stack.size()!=1)
{
Exc_stack();
}
//doublerre=data_stack.top();
cout<<"结果:"<<data_stack.top()<<endl;
data_stack.pop();
}
}
///表达式计算
////数据结构:栈
////作者:ZZJ_4Ever
///////////////////////////////
#include<iostream>
#include<stack>
#include<string>
#include<assert.h>
usingnamespacestd;
stack<double>data_stack;
stack<char>char_stack;
intPRI(char&ch)
{
if(ch==')'){return1;}
elseif(ch=='+'||ch=='-'){return2;}
elseif(ch=='*'||ch=='/'){return3;}
elsereturn0;
}
/*
2.扫描到操作符,与操作符栈的顶端操作符进行比较,
如果优先级小或相等,则弹出数据和操作符进行计算,将结果送入数据栈;
如果优先级较大,则进操作符栈;
如果是’(‘直接进栈,如果是’)’,遇到’(‘则抵消.
*/
voidExc_stack()
{
doubleresult_temp;
assert(char_stack.size()>=1&&data_stack.size()>=1);
doubletemp1=data_stack.top();
data_stack.pop();
doubletemp2=data_stack.top();
data_stack.pop();
charpopchar=char_stack.top();
char_stack.pop();
if(popchar=='+')
result_temp=temp2+temp1;
elseif(popchar=='-')
result_temp=temp2-temp1;
elseif(popchar=='*')
result_temp=temp2*temp1;
elseif(popchar=='/')
result_temp=temp2/temp1;
data_stack.push(result_temp);
}
voidpush_charinto(char&ch)
{
if(ch=='(')//如果是’(‘直接进栈
char_stack.push(ch);
elseif(char_stack.empty())
{
char_stack.push(ch);
}
elseif(PRI(ch)>PRI(char_stack.top()))//如果优先级较大,则进操作符栈
{
char_stack.push(ch);
}
//扫描到操作符
else//如果优先级小或相等,则弹出数据和操作符进行计算,将结果送入数据栈
{
Exc_stack();
if(ch==')')//如果是’)’,遇’(‘直接弹出.
{
while(char_stack.top()!='(')//操作括号内的内容直到遇到'('为止
{
Exc_stack();
}
char_stack.pop();
}
else
//将自己压入栈
char_stack.push(ch);
}
}
voidpush_datainto(double&db)
{
data_stack.push(db);
}
voidmain()
{
stringstr;
while(1)
{
boolflag=false;
doubleret=0.0;
doublen;
cout<<"在此输入表达式:";
//读入
cin>>str;
//处理
//筛选
////////////////////////
/////开始扫描
///////////////////////
for(inti=0;i<str.length();i++)
{
if(str[i]>='0'&&str[i]<='9')
{
if(!flag)
ret=ret*10+str[i]-'0';
else
{
ret=ret+(str[i]-'0')/n;
n*=10;
}
}
elseif(str[i]=='.')
{
n=10;
flag=true;
}
else
{
if(ret!=0||str[i-1]=='0')
push_datainto(ret);
ret=0.0;
flag=false;
push_charinto(str[i]);
}
}
//如果最后一个数字还没有压入栈
if(ret!=0||str[i-1]=='0')push_datainto(ret);
//3.扫描数据完成后,依次退栈并进行计算
assert(!data_stack.empty()||!char_stack.empty());
while(data_stack.size()!=1)
{
Exc_stack();
}
//doublerre=data_stack.top();
cout<<"结果:"<<data_stack.top()<<endl;
data_stack.pop();
}
}
本文地址:http://www.45fan.com/a/luyou/67401.html