1384 - 计算表达式
对于一个不存在括号的表达式进行计算
Input
存在多种数据，每组数据一行，表达式不存在空格
Output
输出结果
Examples
Input
6/2+3+3*4 734/2-56*2-7*8
Output
18 199
Solution C
#include<stdio.h> #include<math.h> #include<malloc.h> typedef struct Node { char data; int da; struct Node *next; }Node; typedef struct Lstack { struct Node *top; }Lstack; int Init(Lstack *s) { if(!s) return 0; else { s->top=NULL; return 1; } } int Empty(Lstack s) { return !s.top; } int Push1(Lstack *s,int e) { Node *newn=(Node*)malloc(sizeof(Node)); if(!newn) return 0; else { newn->da=e; newn->next=s->top; s->top=newn; return 1; } } int Push2(Lstack *s,char e) { Node *newn=(Node*)malloc(sizeof(Node)); if(!newn) return 0; else { newn->data=e; newn->next=s->top; s->top=newn; return 1; } } int Pop1(Lstack *s,int *e) { if(Empty(*s)) return 0; else { Node *p=s->top; *e=p->da; s->top=p->next; free(p); return 1; } } int Pop2(Lstack *s,char *e) { if(Empty(*s)) return 0; else { Node *p=s->top; *e=p->data; s->top=p->next; free(p); return 1; } } int Get(Lstack s,char *e) { if(Empty(s)) return 0; else { *e=s.top->data; return 1; } } void main() { Lstack sta,ch; Init(&sta); Init(&ch); char e,op; char b[100]; char c[100]; int a[100]; int i,j,k,r,legth; int x,y,sum; while(gets(b)!=NULL) { i=0; for(j=0;b[j]!='\0';i++) { for(r=0;b[j]>='0'&&b[j]<='9'&&b[j]!='\0';j++) r++; a[i]=0; for(k=0;k<r;k++) { a[i]=a[i]+(b[j-1-k]-48)*pow(10,k); } if(b[j]!='\0') { c[i]=b[j]; j++; } } legth=i-1; Push1(&sta,a[0]); Push2(&ch,c[0]); Push1(&sta,a[1]); for(i=1;i<legth;i++) { if(c[i]=='*'||c[i]=='/') { Get(ch,&e); if(e=='+'||e=='-') { Push2(&ch,c[i]); Push1(&sta,a[i+1]); Pop1(&sta,&x); Pop1(&sta,&y); Pop2(&ch,&op); switch(op) { case'*':sum=y*x;break; case'/':sum=y/x;break; case'+':sum=y+x;break; case'-':sum=y-x;break; default:break; } Push1(&sta,sum); } else if(e=='*'||e=='/') { Pop1(&sta,&x); Pop1(&sta,&y); Pop2(&ch,&op); switch(op) { case'*':sum=y*x;break; case'/':sum=y/x;break; case'+':sum=y+x;break; case'-':sum=y-x;break; default:break; } Push1(&sta,sum); Push2(&ch,c[i]); Push1(&sta,a[i+1]); } } else if(c[i]=='+'||c[i]=='-') { Pop1(&sta,&x); Pop1(&sta,&y); Pop2(&ch,&op); switch(op) { case'*':sum=y*x;break; case'/':sum=y/x;break; case'+':sum=y+x;break; case'-':sum=y-x;break; default:break; } Push1(&sta,sum); Push2(&ch,c[i]); Push1(&sta,a[i+1]); } } Pop1(&sta,&x); Pop1(&sta,&y); Pop2(&ch,&op); switch(op) { case'*':sum=y*x;break; case'/':sum=y/x;break; case'+':sum=y+x;break; case'-':sum=y-x;break; default:break; } Push1(&sta,sum); printf("%d\n",sum); } }
Solution C++
#include<stdio.h> #include<ctype.h> #include<assert.h> char str[1024]; int a[1024]; int c; int n; int getnum() { int ret=0; while(isdigit(str[c])) { ret=ret*10+str[c]-'0'; c++; } return ret; } int main() { int i,j,s; while(gets(str)) { c=0,s=1; if (str[c]=='-') c++,s=-1; for(j=0;;) { int t=getnum(); while(str[c]=='*' || str[c]=='/') { char op=str[c]; c++; int t1=getnum(); if (op=='*') { t*=t1; } else { assert(t1!=0); assert(t%t1==0); t/=t1; } } a[j++]=s*t; if (str[c]=='-') s=-1; else if (str[c]=='+') s=1; else break; c++; } s=0; for(i=0;i<j;i++) { s+=a[i]; assert(s<1000000000 && s>=-1000000000); } printf("%d\n",s); } return 0; }