首页 > 代码库 > 数据结构 算法3.4（栈的应用） 表达式求值（stl版and数组模拟版）
数据结构 算法3.4（栈的应用） 表达式求值（stl版and数组模拟版）
问题是
输入一串表达式
其中包括 数字 和各种运算符（ +，-，*，/，（，） ）
求它的值
如 4+（5+2*7）*3
stl版：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
int operate(int a,char op,int b)
{
if(op=='+')
return a+b;
if(op=='-')
return a-b;
if(op=='*')
return a*b;
if(op=='/')
return a/b;
}
char precede(char a,char b)
{
if((a=='+'||a=='-')&&(b=='+'||b=='-'||b==')'||b=='#'))
return '>';
if((a=='+'||a=='-')&&(b=='*'||b=='/'||b=='('))
return '<';
if((a=='*'||a=='/')&&(b=='+'||b=='-'||b==')'||b=='#'||b=='*'||b=='/'))
return '>';
if((a=='*'||a=='/')&&b=='(')
return '<';
if(a=='('&&(b=='+'||b=='-'||b=='*'||b=='/'||b=='('))
return '<';
if(a=='('&&b==')')
return '=';
if(a==')'&&(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#'))
return '>';
if(a=='#')
{
if(b=='#')
return '=';
else
return '<';
}
}
bool in(char a)
{
if(a=='+'||a=='-'||a==')'||a=='('||a=='*'||a=='/'||a=='#')
return false;
return true;
}
void work()
{
stack<int>opnd;
stack<char>optr;
char c,ans;
int num=0;
int flag=0;
optr.push('#');
c=getchar();
while(c!='#'||optr.top()!='#')
{
if(in(c))
{
flag=1;
num=num*10+c-'0';
c=getchar();
}
else
{
if(flag==1)
{
flag=0;
opnd.push(num);
num=0;
}
ans=precede(optr.top(),c);
if(ans=='<')
{
optr.push(c);
c=getchar();
}
if(ans=='=')
{
optr.pop();
c=getchar();
}
if(ans=='>')
{
int num1,num2;
char op;
num2=opnd.top();
opnd.pop();
num1=opnd.top();
opnd.pop();
op=optr.top();
optr.pop();
cout<<num1<<' '<<op<<' '<<num2<<endl; //运算顺序
opnd.push(operate(num1,op,num2));
}
}
}
cout<<opnd.top()<<endl; //最终结果
return;
}
int main()
{
work();
return 0;
}
数组模拟版：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
int operate(int a,char op,int b)
{
if(op=='+')
return a+b;
if(op=='-')
return a-b;
if(op=='*')
return a*b;
if(op=='/')
return a/b;
}
char precede(char a,char b)
{
if((a=='+'||a=='-')&&(b=='+'||b=='-'||b==')'||b=='#'))
return '>';
if((a=='+'||a=='-')&&(b=='*'||b=='/'||b=='('))
return '<';
if((a=='*'||a=='/')&&(b=='+'||b=='-'||b==')'||b=='#'||b=='*'||b=='/'))
return '>';
if((a=='*'||a=='/')&&b=='(')
return '<';
if(a=='('&&(b=='+'||b=='-'||b=='*'||b=='/'||b=='('))
return '<';
if(a=='('&&b==')')
return '=';
if(a==')'&&(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#'))
return '>';
if(a=='#')
{
if(b=='#')
return '=';
else
return '<';
}
}
bool in(char a)
{
if(a=='+'||a=='-'||a==')'||a=='('||a=='*'||a=='/'||a=='#')
return false;
return true;
}
void work()
{
int opnd[55];
char optr[55];
char c,ans;
int num=0;
int flag=0;
int opnd_top=0,optr_top=1;
optr[0]='#';
c=getchar();
while(c!='#'||optr[optr_top-1]!='#')
{
if(in(c))
{
flag=1;
num=num*10+c-'0';
c=getchar();
}
else
{
if(flag==1)
{
flag=0;
opnd[opnd_top++]=num;
num=0;
}
ans=precede(optr[optr_top-1],c);
if(ans=='<')
{
optr[optr_top++]=c;
c=getchar();
}
if(ans=='=')
{
optr_top--;
c=getchar();
}
if(ans=='>')
{
int num1,num2;
char op;
num2=opnd[--opnd_top];
num1=opnd[--opnd_top];
op=optr[--optr_top];
cout<<num1<<' '<<op<<' '<<num2<<endl; //运算顺序
opnd[opnd_top++]=operate(num1,op,num2);
}
}
}
cout<<opnd[opnd_top-1]<<endl; //最终结果
return;
}
int main()
{
work();
return 0;
}
数据结构 算法3.4（栈的应用） 表达式求值（stl版and数组模拟版）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。