加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

C语言计算算术表达式（中缀表达式）

(2010-12-22 23:08:55)
标签：

c语言

算术表达式

四则运算

中缀表达式

转

后缀表达式

it

 分类： 编程语言
//    描述: 计算简单的算术表达式 
// 输入：算术表达式（只支持浮点数的加减乘除，表达式以#结尾）
//    输出：计算结果 


#define STACK_FIRST_SIZE 100
#define stack_addment 10

#define MAX_SIZE_OF_EXPRESSION 100 //支持的表达式的最长的字符长度

#include <stdlib.h>
#include "stdio.h"

//定义一个符号栈的结构体
typedef struct
{
   char op[MAX_SIZE_OF_EXPRESSION];
   int top;
}stack_op,*pstack_op;

//将符号栈清空
void clear_stack_op(pstack_op  s){
    s->top=-1;
}

//符号栈压栈
void push_op(pstack_op  s,char c){
    s->top++; 
    s->op[s->top]=c;
}

//弹出符号栈的栈顶元素
char pop_op(pstack_op  s){
    int i=s->top;
    s->top--;
    return s->op[i];
}

//得到符号栈的栈顶元素
char get_op_top(pstack_op  s){
    return s->op[s->top]; 
}

//判断符号栈是否为空
int is_stack_op_empty(pstack_op  s){
    if(s->top==-1){
        return 1;//符号栈为空 
    }else{
        return 0;//符号栈非空 
    }
}


//定义一个栈，存放操作数
typedef struct
{
   float num[MAX_SIZE_OF_EXPRESSION];
   int top;
}stack_num,*pstack_num;

//将操作数栈清空
void clear_stack_num(pstack_num s){
    s->top=-1;
}

//操作数压栈
void push_num(pstack_num  s,float num){
    s->top++; 
    s->num[s->top]=num;
}

//弹出栈顶的操作数 
float pop_num(pstack_num  s){
    int i=s->top;
    s->top--;
    return s->num[i];
}

//得到栈顶操作数
float get_num_top(pstack_num  s){
    return s->num[s->top]; 
}

//判断操作数栈是否为空
int is_stack_num_empty(pstack_num  s){
    if(s->top==-1){
        return 1;//栈为空 
    }else{
        return 0;//栈非空 
    }
}


//判断是否为数字或小数点
int is_digit(char x){
    if((x>='0'&&x<='9')||x=='.')
        return 1;
    return 0;
}



float Operate(float n1,float n2,char c_op)
{
   float r;
   switch(c_op)
   {
     case '+':  r=n1+n2;break;
     case '-':  r=n1-n2;break;
     case '*':  r=n1*n2;break;
     case '/':  r=n1/n2;break;
    }
    return r;
}



//    比较两个操作符的优先级  
char Precede(char c1,char c2){
  if(c1=='+')
  {
    if(c2=='+') return  '>';
    else if(c2=='-') return  '>';
    else if(c2=='*') return  '<';
    else if(c2=='/') return  '<';
    else if(c2=='(') return  '<';
    else if(c2==')') return  '>';
    else return  '>';
   }
  else if(c1=='-')
  {
    if(c2=='+') return  '>';
    else if(c2=='-') return  '>';
    else if(c2=='*') return  '<';
    else if(c2=='/') return  '<';
    else if(c2=='(') return  '<';
    else if(c2==')') return  '>';
    else return  '>';
   }
   else if(c1=='*')
  {
    if(c2=='+') return  '>';
    else if(c2=='-') return  '>';
    else if(c2=='*') return  '>';
    else if(c2=='/') return  '>';
    else if(c2=='(') return  '<';
    else if(c2==')') return  '>';
    else return  '>';
   }
   else if(c1=='/')
  {
    if(c2=='+') return  '>';
    else if(c2=='-') return  '>';
    else if(c2=='*') return  '>';
    else if(c2=='/') return  '>';
    else if(c2=='(') return  '<';
    else if(c2==')') return  '>';
    else return  '>';
   }
   else if(c1=='(')
  {
    if(c2=='+') return  '<';
    else if(c2=='-') return  '<';
    else if(c2=='*') return  '<';
    else if(c2=='/') return  '<';
    else if(c2=='(') return  '<';
    else return  '=';

   }
   else if(c1==')')
  {
    if(c2=='+') return  '>';
    else if(c2=='-') return  '>';
    else if(c2=='*') return  '>';
    else if(c2=='/') return  '>';

    else if(c2==')') return  '>';
    else return  '>';
   }
   else
  {
    if(c2=='+') return  '<';
    else if(c2=='-') return  '<';
    else if(c2=='*') return  '<';
    else if(c2=='/') return  '<';
    else if(c2=='(') return  '<';

    else return  '=';
   }
}


// 中缀表达式转后缀表达式
// 算法思路：中缀、后缀表达式中操作数的次序一致，故扫描到中缀表达式操作数时直接输出即可；对于运算符，视其优先级别，优先级高的运算符先输出（先运算）；设一存放运算符的栈S，先将S置空，存入‘#’。另设中缀表达式已存入数组mid[n] 。依次扫描mid[n]中各分量mid[i]送 x ：
//            若x=操作数，直接输出x；
//            若x=‘#’（结束符），依次输出栈S中运算符，转换结束；
//            若x=‘)’，反复退栈输出S中子表达式运算符,直到栈顶=‘(’，并退掉；
//            若x=运算符，反复退栈输出栈S中运算符，直到栈顶符<x。
//    注意：不同的操作数之间用空格格开
void Mid_Post(const char*  mid_expression,char* post_expression){
int i=1,j=0;
char x,ch_precede;
 
    stack_op st_op;//符号栈 
    clear_stack_op(&st_op);//置空栈
    push_op(&st_op,'#');
    
    while(is_stack_op_empty(&st_op)==0){//符号栈非空 
        x=mid_expression[i];
        if( is_digit(x)){
            do{
                post_expression[j++]=x;
                i++;
                x=mid_expression[i];
            }while(is_digit(x));
            post_expression[j++]=' ';//数字之间用空格格开 
        }else if(x=='#'){
            while(!is_stack_op_empty(&st_op)){//符号栈非空 
                post_expression[j++]=pop_op(&st_op);
            }
        }else if(x==')'){
            while(get_op_top(&st_op)!='('){
                post_expression[j++]=pop_op(&st_op);
            }
            pop_op(&st_op);//将"("弹出 
            i++;
        }else if(x==' '){
            //do nothing 
        }else{
            while((ch_precede=Precede(get_op_top(&st_op),x))!='<'){
                post_expression[j++]=pop_op(&st_op);
            }
            push_op(&st_op,x);
            i++;
        }
    } 
}




//    计算后缀表达式的值 
//    算法思路：设操作数栈st_num,先将其置空,然后扫描后缀表达式中各分量送x；
// 若x=操作数，直接进栈；
// 若x=运算符：b=Pop(&st_num)，a=Pop(&st_num)，作a、b关于x的运算,结果再进栈；
// 若x=‘#’，算法结束，输出栈顶，即表达式结果。
float PostCount(const char * post_expression){
    int i=0,j=0;
    char x;
    char num_temp[MAX_SIZE_OF_EXPRESSION];//临时存放字符型的数字，用来转换成浮点数 
    float y,result,a,b; 
    stack_num st_num;//存放操作数 
    clear_stack_num(&st_num);
    
    while(post_expression[i]!='#'){
        x=post_expression[i];
   if(is_digit(x)){
            do{
                num_temp[j++]=x;
                i++;
                x=post_expression[i];
            }while(x!=' ');
            num_temp[j]='\0';
            y=atof(&num_temp[0]);//转换成数值，进栈
            push_num(&st_num,y);
            j=0;
            i++;
        }else{
            b=pop_num(&st_num); a=pop_num(&st_num);//取两操作数
            result=Operate(a,b,x);
            push_num(&st_num,result);
            i++;
        }
    }
    if(!is_stack_num_empty(&st_num)){
       return get_num_top(&st_num);
    } 
    
}

int main()
{
    //定义两个数组用来存放中缀和后缀表达式
char mid_expression[MAX_SIZE_OF_EXPRESSION],post_expression[MAX_SIZE_OF_EXPRESSION]; 
char if_continue='y';//用来判断是否继续 
    char ch_in;//用来存储读入的字符 
float result=0.0;
int i=1;
while(if_continue=='y'||if_continue=='Y'){
mid_expression[0]='#';
printf("请输入表达式，以#号结束:\n"); 
fflush(stdin); //清空缓存区
while(ch_in=getchar()){
            if(i< MAX_SIZE_OF_EXPRESSION){
                mid_expression[i++]=ch_in;
            }else{
                printf("输入的表达式超出范围,请输入长度小于%d的表达式\n",MAX_SIZE_OF_EXPRESSION);
                system("pause");
                return -1; 
            }
            if(ch_in=='#'){
                break;
            }
        }
        fflush(stdin); //清空缓存区
        i=1;
        
    
        
        
Mid_Post(mid_expression,post_expression);
        
result=PostCount(post_expression);
   printf("计算结果为:%f\n",result); 
   
        printf("要继续吗?Y/N:");
        scanf("%c",&if_continue);
}
system("pause");
return 0;
}











喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有