后缀表达式由于其特殊性只需要操作数栈,不需要运算符栈,每当出现运算符就说明是对前面两个操作数进行操作
#include<bits/stdc++.h>
using namespace std;
char tok[30][20];
int tok_max;
int pos=1;
int main(){
tok_max=0;
int num1=0;
for(;;){
int c=getchar();
if(c=='@')break;
if(c=='+'||c=='-'||c=='*'||c=='/'){
tok[++tok_max][0]=c;
}else if(c=='.'){
sprintf(tok[++tok_max],"%d",num1);
num1=0;
}else{
num1=num1*10+(c-'0');
}
}
// for(int i=1;i<=tok_max;i++){
// puts(tok[i]);
// }
stack<int>st;
for(int i=1;i<=tok_max;i++){
//操作数
if(isdigit(*tok[i])){
int num2;
sscanf(tok[i],"%d",&num2);
st.push(num2);
}
//运算符
else if(*tok[i]=='+'){
int num3=st.top();st.pop();
int num4=st.top();st.pop();
int num5=num4+num3;
st.push(num5);
}
else if(*tok[i]=='-'){
int num3=st.top();st.pop();
int num4=st.top();st.pop();
int num5=num4-num3;
st.push(num5);
}
else if(*tok[i]=='*'){
int num3=st.top();st.pop();
int num4=st.top();st.pop();
int num5=num4*num3;
st.push(num5);
}
else if(*tok[i]=='/'){
int num3=st.top();st.pop();
int num4=st.top();st.pop();
int num5=num4/num3;
st.push(num5);
}
}
printf("%d\n",st.top());
return 0;
}
前缀表达式
前缀表达式用栈写相对麻烦,但由于运算符前置,可以方便地将其转化为二叉树,递归实现
#include<bits/stdc++.h>
using namespace std;
char tok[6000][30];
int tok_max;
int pos=1;
struct TREE{
double val;
char op;
struct TREE *l,*r;
}tr;
void build_tree(struct TREE *tr){
if(isdigit(*tok[pos])){
sscanf(tok[pos],"%lf",&(tr->val));
//tr->val=atof(tok[pos]);
pos++;
tr->l=NULL;tr->r=NULL;
return;
}
else{
tr->op=*tok[pos];
pos++;
tr->l=(struct TREE*)malloc(sizeof(struct TREE));
tr->r=(struct TREE*)malloc(sizeof(struct TREE));
build_tree(tr->l);build_tree(tr->r);
return;
}
}
/*
void x(struct TREE *tr){
if(tr==NULL)return;
x(tr->l);
if(tr->l==NULL && tr->r==NULL){
printf("%f ",tr->val);
}else{
printf("%c ",tr->op);
}
x(tr->r);
}*/
double calc(struct TREE *tr){
if(tr->l==NULL && tr->r==NULL){ //是操作数
return tr->val;
}
else{
if(tr->op=='+')return calc(tr->l)+calc(tr->r);
if(tr->op=='-')return calc(tr->l)-calc(tr->r);
if(tr->op=='*')return calc(tr->l)*calc(tr->r);
if(tr->op=='/')return calc(tr->l)/calc(tr->r);
}
}
int main(){
tok_max=1;
for(;;){
int num=scanf("%s",tok[tok_max]);
if(num==EOF)break;
tok_max++;
}
build_tree(&tr);
//x(&tr);
double ans=calc(&tr);
printf("%f\n",ans);
return 0;
}
PS:以上代码经常出现*tok[i]
一类的表达,因为tok[i]
可看做指向数组的指针,*tok[i]
等价于tok[i][0]
,写起来简洁易懂