c语言，中缀表达式转后缀表达式并计算

佚名 6年前 (2019-04-18) 随笔 863人围观抢沙发百度已收录

  1 //c语言中缀表达式计算
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <string.h>
  5 #include <stdbool.h>
  6 #include <math.h>
  7 typedef struct{
  8     char data[85];
  9     int top;
 10 }stack;
 11 typedef struct{
 12     int data[85];
 13     int top;
 14 }nstack;
 15 int priority(char);
 16 char pop(stack*);
 17 int npop(nstack*);
 18 int ntop(nstack*);
 19 char top(stack*);
 20 void push(stack*,char);
 21 void npush(nstack*,char);
 22 bool isnumber(char);
 23 bool isempty(stack*);
 24 int main(void){
 25     int i,j,len,cnt;
 26     stack *st=(stack*)malloc(sizeof(stack));
 27     nstack *nst=(nstack*)malloc(sizeof(nstack));
 28     
 29     char str[85];
 30     char out[85];
 31     
 32     scanf("%s",str);
 33     
 34     nst->top=-1;
 35     st->top=-1;
 36     cnt=0;
 37     len=strlen(str);
 38     
 39     for(i=0;i<len;i++)
 40     {
 41         if(isnumber(str[i]))
 42             out[cnt++]=str[i];
 43         else
 44         {
 45             //
 46             if(str[i]=='('||isempty(st))
 47             {
 48                 push(st,str[i]);
 49                 continue;
 50             }
 51             //
 52             if(str[i]==')')
 53             {
 54                 while(top(st)!='(')
 55                 {
 56                     out[cnt++]=top(st);
 57                     pop(st);
 58                 }
 59                 pop(st);
 60                 continue;
 61             }
 62             //
 63             while(!isempty(st)&&top(st)!='('&& priority(str[i])<=priority(top(st)))
 64             {
 65                 out[cnt++]=top(st);
 66                 pop(st);
 67             }
 68             //
 69             push(st,str[i]);
 70         }
 71     }
 72     while(!isempty(st)){
 73         out[cnt++]=top(st);
 74         pop(st);
 75     }
 76     out[cnt]='\0';
 77     for(i=0;i<cnt;++i)
 78         printf("%c ",out[i]);
 79     printf("\n");
 80     for(i=0;i<cnt;i++)
 81     {
 82         if(isnumber(out[i])){
 83             npush(nst,out[i]);
 84             continue;
 85         }else if(out[i]=='+'){
 86             nst->data[nst->top-1]+=ntop(nst);
 87             npop(nst);
 88         }else if(out[i]=='-'){
 89             nst->data[nst->top-1]-=ntop(nst);
 90             npop(nst);
 91         }else if(out[i]=='*'){
 92             nst->data[nst->top-1]*=ntop(nst);
 93             npop(nst);
 94         }else if(out[i]=='/'){
 95             nst->data[nst->top-1]/=ntop(nst);
 96             npop(nst);
 97         }else if(out[i]=='^'){
 98             nst->data[nst->top-1]=pow(nst->data[nst->top-1],ntop(nst));
 99             npop(nst);
100         }
101         for(j=0;j<=nst->top;++j)
102             printf("%d ",nst->data[j]);
103         for(j=i+1;j<cnt;++j)
104             printf("%c ",out[j]);
105         printf("\n");
106     }
107     return 0;
108 }
109 bool isnumber(char ch){
110     if(ch>='0'&&ch<='9')
111         return true;
112     else
113         return false;
114 }
115 bool isempty(stack *s){
116     if(s->top==-1)
117         return true;
118     else
119         return false;
120 }
121 void push(stack *s,char ch){
122     s->data[++s->top]=ch;
123 }
124 void npush(nstack *s,char ch){
125     s->data[++s->top]=ch-'0';
126 }
127 char pop(stack *s){
128     return s->data[s->top--];
129 }
130 int npop(nstack *s){
131     return s->data[s->top--];
132 }
133 int priority(char ch){
134     if(ch=='(')
135         return 0;
136     if(ch=='+'||ch=='-')
137         return 1;
138     if(ch=='*'||ch=='/')
139         return 2;
140     if(ch=='^')
141         return 3;
142     return 0;
143 }
144 char top(stack *s){
145     return s->data[s->top];
146 }
147 int ntop(nstack *s){
148     return s->data[s->top];
149 }