数据结构c语言版,栈实现表达式求值
发布网友
发布时间：2022-05-10 18:41
共2个回答
热心网友
时间：2023-10-22 11:00
搞两个栈，一个存数字，一个存符号，处理一下优先级就可以了。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<string>
int a[10][10]={{3,2,2,3,3},{3,3,2,3,3},{2,2,2,1,0},{3,3,0,3,3},{2,2,2,0,1}};
char t[100];
using namespace std;
struct node
{
int h;
char c;
node *p;
};
int pd(char ch)
{
if((ch=='+')||(ch=='-'))return 0;
if((ch=='*')||(ch=='/'))return 1;
if(ch=='(')return 2;
if(ch==')')return 3;
if(ch=='@')return 4;
}
int main()
{
node *r,*q;
int i,l,k=0,v,w,o;
string s;
cin>>s;
l=s.length();
s[l]='@';
l++;
q=new node;
q->c='@';
for(i=0;i<=l-1;i++){
if((s[i]>='0')&&(s[i]<='9')){
t[k]=s[i];
k++;
if((s[i+1]<'0')||(s[i+1]>'9')){
t[k]=' ';
k++;
}
continue;
}
w=pd(s[i]);
v=pd(q->c);
switch (a[v][w]){
case 1:
q=q->p;
break;
case 2:
r=q;
q=new node;
q->c=s[i];
q->p=r;
break;
case 3:
r=q;
q=new node;
q->c=s[i];
q->p=r;
while(a[v][w]==3){
t[k]=q->p->c;
k++;
q->p=q->p->p;
v=pd(q->p->c);
w=pd(q->c);
}
if(a[v][w]==1)
q=q->p->p;
break;
}
}
q=new node;
for(i=0;i<=k-1;i++){
if(((t[i]>'9')||(t[i]<'0'))&&(t[i-1]>='0')&&(t[i-1]<='9')){
o=1;
v=i-1;
w=0;
while(t[v]>='0'){
w=w+o*(t[v]-'0');
o=o*10;
v--;
}
r=q;
q=new node;
q->h=w;
q->p=r;
}
switch(t[i]){
case '+':
q->p->h+=q->h;
q=q->p;
break;
case '-':
q->p->h-=q->h;
q=q->p;
break;
case '*':
q->p->h*=q->h;
q=q->p;
break;
case '/':
q->p->h/=q->h;
q=q->p;
break;
}
}
cout<<q->h;
return 0;
}
热心网友
时间：2023-10-22 11:01
