求前缀表达式的值

7-1 求前缀表达式的值（20 分）

+ + 2 * 3 - 7 4 / 8 4 

13.0

法一

提交结果

#include       #include         #include           #include             #include               #include                 using namespace std; stack                   q; int main(){ string a[100]; bool error = 0; int n = 0; while(cin>>a[n++]){}///读到文件结尾自动结束 n -= 1;///注意这里n是个数，需要减一，可自己尝试确认 for(int i = n-1; i>=0; i--){ ///如果是符号 if(a[i].length() == 1 && (a[i][0]== '+' || a[i][0]=='-' || a[i][0]=='*' || a[i][0]=='/')){ if(q.size()<2) {error = 1; break;} double aa = q.top(); q.pop(); double bb = q.top(); q.pop(); if(a[i][0]== '+') q.push(aa+bb); else if(a[i][0]== '-') q.push(aa-bb); else if(a[i][0]== '*') q.push((aa*bb)); else if(a[i][0]== '/') { if(bb==0){error = 1; break;} q.push(aa/bb); } } else{ /// c_str() 函数是转化为字符数组 ///atof() 是c语言中将字符数组转化为浮点型数据函数 double x = atof(a[i].c_str()); q.push(x); } } if(q.size() != 1) error = 1; if(error) printf("ERROR"); else printf("%.1f",q.top()); return 0; }                                          

法二

/* 求前缀表达式的值 */ #include 
   
     #include 
    
      #include 
     
       #include 
      
        #define N 30 #define TRUE 1 #define FALSE 0 typedef struct { double data[N]; int top; } Stack; /* 入栈 */ void Push( Stack *ptrs, double item ) { if( ptrs->top == N - 1 ){ printf( "Stack is full.\n" ); return; } else { ptrs->data[ ++( ptrs->top ) ] = item; return; } } /* 岀栈 */ double Pop( Stack * ptrs ) { if( ptrs->top == -1 ) { printf( "Stack is empty.\n" ); return; } else return ptrs->data[ ( ptrs->top )-- ]; } /* 判断是否操作符 */ int IsOperator( char ch ) { if( ch == '+' || ch == '-' || ch == '*' || ch == '/' ) return TRUE; else return FALSE; } /* 计算 */ double Calculate( double a, double b,char ch ) { switch( ch ) { case '+' : return a + b; break; case '-' : return a - b; break; case '*' : return a * b; break; case '/' : return a / b; } } int main() { char expr[N]; gets( expr ); int len = strlen( expr ); Stack ss; ss.top = -1; double cc = 1; double tem_sum = 0; double operand_a; double operand_b; double result; int error = 0; // 记录除数为0的错误情况 int i; for( i = len - 1; i >= 0; -- i ) { if( expr[i] >= '0' && expr[i] <= '9' ) { tem_sum += ( expr[i] - '0' ) * cc; cc *= 10; if( expr[i-1] == '+' ) { //printf( "%d\n", tem_sum ); Push( &ss, tem_sum ); tem_sum = 0; cc = 1; i -= 2; // 跳过下一个正号和空格 continue; } else if( expr[i-1] == '-' ) { tem_sum = -tem_sum; //printf( "%d\n", tem_sum ); Push( &ss, tem_sum ); tem_sum = 0; i -= 2; // 跳过下一个负号和空格 continue; } else if( expr[i-1] == ' ' ) { // 一个数字处理完了 //printf( "%d\n", tem_sum ); Push( &ss, tem_sum ); tem_sum = 0; cc = 1; i --; continue; } } else if( expr[i] == '.' ) { tem_sum /= cc * 1.0; cc = 1; } else if( IsOperator( expr[i] ) ) { operand_a = Pop( &ss ); operand_b = Pop( &ss ); if( expr[i] == '/' && operand_b == 0 ) { error = 1; break; } else { result = Calculate( operand_a, operand_b, expr[i] ); //printf( "result:%.1lf\n", result ); Push( &ss, result ); i--; // 跳过下一个空格 } } } if( error != 1 ) printf( "%.1lf\n", Pop( &ss ) ); else printf( "ERROR\n" ); return 0; } 
       
      
     
   

法三

（用c++编译器才行）

求前缀表达式的算法不难，这题合适的数据结构显然是栈。这题稍复杂的地方就是对输入的处理以及栈的基本操作。

首先，输入的每一项数据存储在栈的每一个节点中这是确定的。但是所输入的数据的类型却不一致。栈的节点struct Node里设计了四个成员变量。
struct Node{

char opr;
float num;
int type; //用来标记该节点是个操作符还是操作数
struct Node* Next;
};

我们最终要把所输入的操作符以char形式存储，所输入的操作数以float形式存储。

这里，先统一以字符串形式通过scanf(“%s”)输入，用空格隔开。然后再判断该字符串是表示操作数还是操作符，并通过设计两个相应函数把字符串转化为字符形式的操作符 以及 把字符串转化为float操作数。

每输入一项数据后，都要对栈进行相应操作。
如果输入的是操作符则push。
如果当前输入的是操作数则分两种情况。
0. 此时是空栈，直接push进栈。
1. 此时栈顶是操作符，则直接push进栈。
2. 此时栈顶也是操作数，即连续出现了两个操作数，那么弹出栈顶的操作数（而后栈顶指针已变），再弹出栈顶的操作符。通过这个操作数、操作符以及当前输入的操作数计算得出一个新的操作数。此时再把这个新的操作数压入栈中，进栈操作同样递归地进行栈顶是符号还是数字的判断，直至可直接push进栈。
最后栈顶操作数即为前缀表达式的结果。

除此之外，需注意的细节有：
1. 注意ERROR情况的出现，进行除法操作前判断作为除数的操作数是否为零。
2. 成员变量Next未显式赋值的时候并没有默认为NULL

#include 
   
     #include 
    
      #include 
     
       #include 
      
        typedef struct Node* Stack; typedef struct Node* Position; struct Node{ char opr; float num; int type; //0表示操作符 1表示数字 struct Node* Next; }; void Push(char c, Stack S) { Position P; Position Temp; Temp = (Position)malloc(sizeof(struct Node)); Temp->opr = c; Temp->type = 0; Temp->Next = NULL; Temp->Next = S->Next; S->Next = Temp; } int IsEmpty(Stack S) { return S->Next == NULL; } float PopNum(Stack S) { Position Temp; float num; Temp = S->Next; num = Temp->num; S->Next = Temp->Next; free(Temp); return num; } char PopOpr(Stack S) { Position Temp; char opr; Temp = S->Next; opr = Temp->opr; if (Temp->Next != NULL) S->Next = Temp->Next; else S->Next = NULL; free(Temp); return opr; } void Push(float n, Stack S) { Position P; Position Temp; Temp = (Position)malloc(sizeof(struct Node)); Temp->num = n; Temp->type = 1; Temp->Next = NULL; if (S->Next == NULL) //如果此前一个是操作符或栈空，那么直接压入 { Temp->Next = S->Next; S->Next = Temp; } else if (S->Next->type == 0) { Temp->Next = S->Next; S->Next = Temp; } else{ //如果此前一个是数字 //char c = S->Next->Next->opr; float m = PopNum(S); char c = PopOpr(S); if (c == '+') Push(n + m, S); else if (c == '-') Push(m - n, S); else if (c == '*') Push(m * n, S); else{ if (n == 0) { printf("ERROR"); exit(0); } else Push(m / n, S); } } } int IsOpr(char in[]) { int length = strlen(in); if (length==1 && (in[0] == '+' || in[0] == '-' || in[0] == '*' || in[0] == '/')) return 1; else return 0; } float StrToNum(char s[]) { int length = strlen(s); float result = 0; int flag = 1; int right = 0; int j = 0; for (int i = 0; i < length; i++) { if (s[i] == '.'){ right = 1; continue; } if (i == 0 && s[i] == '+') flag = 1; else if (i == 0 && s[i] == '-') flag = -1; else if (!right) { result = 10 * result + s[i] - '0'; } else{ j++; result = result + (s[i] - '0') / (pow(10.0, j)); } } return result*flag; } void PrintStack(Stack S) { Position P; P = S->Next; while (P != NULL) { if (P->type == 0) { printf("%c", P->opr); } else printf("%f", P->num); P = P->Next; } printf("\n"); } int main() { char in[30]; char buff; float result = 0; Stack S; S = (Stack)malloc(sizeof(struct Node)); S->Next = NULL; scanf("%s", in); buff = getchar(); if (!IsOpr(in)) //如果输入的第一项就是数字，那这个数字就是结果 { float r = StrToNum(in); printf("%.1f", r); return 0; } //如果输入的第一项是操作符 Push(in[0], S); while (buff != '\n') { scanf("%s", in); if (IsOpr(in)) //如果输入的是操作符，就直接入栈 { Push(in[0], S); } else //如果输入的数字 { Push(StrToNum(in), S); } buff = getchar(); } //PrintStack(S); result = S->Next->num; printf("%.1f", result); return 0; } 
       
      
     
   

法四

提交结果

思路  
关键就是读取数据的部分，因为+ -（加减） 会被%d（当做正负）给读走，导致错误。所以不能直接使用if(!scanf(%d))scanf(%c).

#include 
     
       #include 
      
        #include 
       
         typedef struct node *Node; struct node { float num; char operators; int flag;//0-int,1-char Node Next; }; Node ReadData(void); Node Function(Node); float Coculate(char,float,float); int main() { struct node head; Node temp=&head; do { temp->Next=ReadData(); temp=temp->Next; } while(getchar()!='\n'); temp->Next=NULL; temp=&head; while(temp->Next) { if(temp->Next&&temp->Next->Next&&temp->Next->Next->Next) { if(temp->Next->flag==1&&temp->Next->Next->flag==0&&temp->Next->Next->Next->flag==0) { float sum=Coculate(temp->Next->operators,temp->Next->Next->num,temp->Next->Next->Next->num); if(sum==99999)break; temp->Next->Next->Next->num=sum; temp->Next=temp->Next->Next->Next; // printf("[%.1f]",temp->Next->num); temp=&head; } else temp=temp->Next; } else break; } if(head.Next->Next) { printf("ERROR"); } else printf("%.1f",head.Next->num); return 0; } float Coculate(char c,float a,float b) { float sum; switch(c) { case '+': sum=a+b; break; case '-': sum=a-b; break; case '*': sum=a*b; break; case '/': if(!b)return 99999; sum=a/b; break; default : sum=99999; break; } return sum; } Node ReadData(void) { char a[31]; Node temp=(Node)malloc(sizeof(struct node)); scanf("%s",a); int len=strlen(a); if(len==1) { switch(a[0]) { case '+': case '-': case '*': case '/': temp->operators=a[0]; temp->flag=1; break; default: temp->num=a[0]-'0'; temp->flag=0; break; } } else { temp->num=0; temp->flag=0; if(a[0]>='0'&&a[0]<='9') { int i=0; for(; i 
        
          num*=10; temp->num+=a[i]-'0'; } float xiaoshu=1; for(++i; i 
         
           num+=xiaoshu*(a[i]-'0'); } } else { int i=1; for(; i 
          
            num*=10; temp->num+=a[i]-'0'; } float xiaoshu=1; for(++i; i 
           
             num+=xiaoshu*(a[i]-'0'); } if(a[0]=='-')temp->num*=-1; } } return temp; } 
            
           
          
         
        
       
     

编译器输出：a.c: In function ‘ReadData’:
a.c:69:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf(“%s”,a);

     ^~~~~~~~~~~~~

法五

提交结果

计算前缀表达式的过程和计算后缀表达式式的过程相反，它是从后向前扫描的。

#include 
         
           #include 
          
            #include 
           
             #include 
            
              using namespace std; float oper(float f1,float f2, char op) { if(op=='+') return f1+f2; else if(op=='-') return f1-f2; else if(op=='*') return f1*f2*1.0; else if(op=='/') return f1*1.0/f2; } int main() { stack 
             
               s; string prefixExp; getline(cin,prefixExp); int strLen=prefixExp.length(); int temp,i,j; int t1,t2; for(i=strLen-1;i>=0;i--) { string digitStr=""; if(prefixExp[i]=='+' || prefixExp[i]=='-' || prefixExp[i]=='*' || prefixExp[i]=='/') //运算符 { t1=s.top(); s.pop(); t2=s.top(); s.pop(); if(t2==0 && prefixExp[i]=='/') { printf("ERROR\n"); return 0; } s.push(oper(t1,t2,prefixExp[i])); // printf("%f\n",s.top()); i--;//下一位肯定是空格 } else //运算数 { while(i>=0 && prefixExp[i]!=' ') //不要漏掉i>=0条件 { digitStr=prefixExp[i]+digitStr; i--; } //printf("atof:%f\n",atof(digitStr.c_str())); s.push(atof(digitStr.c_str())); } } if(s.size()==1) printf("%0.1f\n",s.top()); else printf("ERROR\n"); return 0; }