【问题描述】
设计一个程序，实现简单整数的四则运算（运算对象不小于0），包括加减乘除和小括号。
【输入形式】
每行输入一个运算表达式（假设表达式均为正确的表达式），以#作为表达式结束。（表达式长度不超过80）
【输出形式】
输出表达式的后缀式
输出运算结果
【样例输入】
23-(2-4)*2+36/(20-14)#
(100-23)/6+2*(13-9)-40#
((100-20)*2)-35#
120+30+50#
【样例输出】
23 2 4 - 2 * - 36 20 14 - / +
33
100 23 - 6 / 2 13 9 - * + 40 -
-20
100 20 - 2 * 35 -
125
120 30 + 50 +
200

方法一

在方法一中呢我们定义两个主要函数，再在主函数中使用两个函数，最终求出表达式的值
一个函数用来求出原式子的后缀式
另一个函数用来进行后缀式的计算

1.1 后缀式的转换

后缀式的转换是个老生常谈的问题了，对于这个问题一定不能忘了要先设置运算符的优先级

int f(char s){     //我们需要先设置运算符的优先级
    if(s=='#') return -1;
    else if(s=='('||s==')') return 0;
    else if(s=='+'||s=='-') return 1;
    else if(s=='*'||s=='/') return 2;
}
int Change(char *s1,char *s2){    
    int i=0,e;
    PStack S;         
    S=Init_Stack();
    Push_Stack(S,'#');      //初始化栈，置栈底为#
    while(*s1!='#'){   //因为输入#结束，所以最后一个输入的字符是#,当遇到#终止循环
        if(*s1>='0'&&*s1<='9'){    //遇到非运算符的时候
            while(*s1>='0'&&*s1<='9'){   //当有连续的非运算符，我们需要把他们放到一起
                s2[i++]=*s1;
                s1++;
            }
            s2[i++]=' ';    //用空格将
 
 
 
不同元素隔开，方便后缀式的计算
            s1--;    //这里的s1--千万不能少！！
        }else{              //当遇到运算符时
            Get_Stack(S,&e);     //获取栈顶元素
            if((f(*s1)>f(e)&&*s1!=')')||*s1=='('){   //如果优先级大于栈顶元素且不是")"
                Push_Stack(S,*s1);            //或者遇到了"("，直接入栈
            }else if(*s1==')'){       //如果读取的字符是")"，先出栈，再判断
                Pop_Stack(S,&e);       
                while(e!='('){        //遇到非"("的运算符放入后缀式
                    s2[i++]=e;        //遇到"("出栈后不用放到后缀式
                    s2[i++]=' ';
                    Pop_Stack(S,&e);
                }
            }else{    //当运算符优先级小于栈顶元素时，出栈放入后缀式直到大于栈顶元素
                while(f(*s1)<=f(e)){    
                    Pop_Stack(S,&e);
                    s2[i++]=e;
                    s2[i++]=' ';
                    Get_Stack(S,&e);
                }
                Push_Stack(S,*s1);    //入栈
            }
        }
        s1++;
    }
    while(!Empty_Stack(S)){    //将栈中剩余运算符都放入后缀式
        Pop_Stack(S,&e);
        s2[i++]=e;
    }
    int k=0;
    while(1){
        if(s2[k]=='#') break;
        printf("%c",s2[k++]);    //打印后缀式
    }
    printf("\n");
    return 1;
}

1.2 计算后缀式

计算后缀式的方法是遍历后缀式，每遇到数字字符入栈，遇到运算符时从栈中取两个元素，进行计算，将计算结果放入栈中，用于下一次计算

int Match(char *s){
    int a,b,x;
    PStack S;
    S=Init_Stack();    //初始化一个栈
    while(*s!='\0'){    //循环
        if(*s>='0'&&*s<='9'){   //当遇到数字字符时
            x=0;
            while(*s>='0'&&*s<='9'){   //使用此方法将字符串转换成整型变量，用于计算
                x=*s-'0'+x*10;
                s++;
            }
            Push_Stack(S,x);    //入栈
        }else if(*s!=' '){     //当遇到非空格且不是数字字符时
            Pop_Stack(S,&a);   //出栈一个数字
            Pop_Stack(S,&b);   //再出栈一个数字
            switch(*s){       //进行运算，将运算结果放入栈中
                case '+':x=a+b;break;
                case '-':x=b-a;break;
                case '*':x=a*b;break;
                case '/':x=b/a;break;
            }
            Push_Stack(S,x);  
        }
        s++;
    }
    Pop_Stack(S,&x);  //最后出栈，打印最后一个元素即是表达式的解
    printf("%d",x);
    return 1;
}

1.3 完整代码

#include<stdio.h>
#include<malloc.h>
typedef struct Stack{
    int data;
    struct Stack * next;
}Stack,*PStack;
PStack Init_Stack(){
    PStack S=(PStack)malloc(sizeof(Stack));
    S->next=NULL;
    return S;
}
int Empty_Stack(PStack S){
    if(!S->next) return 1;
    else return 0;
}
int Push_Stack(PStack S,int e){
    PStack P=(PStack)malloc(sizeof(Stack));
    P->data=e;
    P->next=NULL;
    P->next=S->next;
    S->next=P;
    return 1;
}
int Pop_Stack(PStack S,int *e){
    if(!S->next) return 0;
    *e=S->next->data;
    S->next=S->next->next;
    return 1;
}
int Get_Stack(PStack S,int *e){
    if(!S->next) return 0;
    *e=S->next->data;
    return 1;
}
int f(char s){
    if(s=='#') return -1;
    else if(s=='('||s==')') return 0;
    else if(s=='+'||s=='-') return 1;
    else if(s=='*'||s=='/') return 2;
}
int Change(char *s1,char *s2){
    int i=0,e;
    PStack S;
    S=Init_Stack();
    Push_Stack(S,'#');
    while(*s1!='#'){
        if(*s1>='0'&&*s1<='9'){
            while(*s1>='0'&&*s1<='9'){
                s2[i++]=*s1;
                s1++;
            }
            s2[i++]=' ';
            s1--;
        }else{
            Get_Stack(S,&e);
            if((f(*s1)>f(e)&&*s1!=')')||*s1=='('){
                Push_Stack(S,*s1);
            }else if(*s1==')'){
                Pop_Stack(S,&e);
                while(e!='('){
                    s2[i++]=e;
                    s2[i++]=' ';
                    Pop_Stack(S,&e);
                }
            }else{
                while(f(*s1)<=f(e)){
                    Pop_Stack(S,&e);
                    s2[i++]=e;
                    s2[i++]=' ';
                    Get_Stack(S,&e);
                }
                Push_Stack(S,*s1);
            }
        }
        s1++;
    }
    while(!Empty_Stack(S)){
        Pop_Stack(S,&e);
        s2[i++]=e;
    }
    int k=0;
    while(1){
        if(s2[k]=='#') break;
        printf("%c",s2[k++]);
    }
    printf("\n");
    return 1;
}
int Match(char *s){
    int a,b,x;
    PStack S;
    S=Init_Stack();
    while(*s!='\0'){
        if(*s>='0'&&*s<='9'){
            x=0;
            while(*s>='0'&&*s<='9'){
                x=*s-'0'+x*10;
                s++;
            }
            Push_Stack(S,x);
        }else if(*s!=' '){
            Pop_Stack(S,&a);
            Pop_Stack(S,&b);
            switch(*s){
                case '+':x=a+b;break;
                case '-':x=b-a;break;
                case '*':x=a*b;break;
                case '/':x=b/a;break;
            }
            Push_Stack(S,x);
        }
        s++;
    }
    Pop_Stack(S,&x);
    printf("%d",x);
    return 1;
}
int main(){
    char s1[100],s2[100];
    scanf("%s",s1);
    Change(s1,s2);
    Match(s2);
    return 0;
}

方法二

在方法二中我们只定义了一个计算函数，然后在主函数中边转换后缀式边进行计算（这样大大提高了计算效率）

2.1 计算函数

我们设计一个计算函数，用于后缀式的计算

int match(SqStack *s,char s2)   //函数需要两个参量
{                              //一个是栈，另一个是字符
    int a,b;          
    ElemType e;
    switch(s2)        //定义每一种字符的运算规则
    {
        case '+':            
            GetTop(s,&b);      
            Pop(s,&e);
            GetTop(s,&a);
            Pop(s,&e);
            Push(s,a+b);
            break;
        case '-':
            GetTop(s,&b);
            Pop(s,&e);
            GetTop(s,&a);
            Pop(s,&e);
            Push(s,a-b);
            break;
        case '*':
            GetTop(s,&b);
            Pop(s,&e);
            GetTop(s,&a);
            Pop(s,&e);
            Push(s,a*b);
            break;
        case '/':
            GetTop(s,&b);
            Pop(s,&e);
            GetTop(s,&a);
            Pop(s,&e);
            Push(s,a/b);
            break;
        case '#':break;    
    }
}

2.2 主函数

在主函数中，我们边进行后缀式转换，边进行表达式的计算，大大节省了程序运行的时间

int  main()
{
 
    char s[100];
    while(gets(s))
    {
        SqStack s1,s2;
        InitStack(&s1);   //第一个栈用于转换后缀式
        InitStack(&s2);   //第二个栈用于计算后缀式
        Push(&s1,'#');
        int i;
        for(i=0;i<strlen(s);i++)
        {
            if(s[i]==')')
            {
                ElemType e;
                while(GetTop(&s1,&e)&&e!='(')
                {
                    printf("%c ",e);      //遇到字符进行运算
                    match(&s2,e);
                    Pop(&s1,&e);     //取出这个字符
                }
                Pop(&s1,&e);    //遇到"("时取出就好
            }
            else if(s[i]>='0'&&s[i]<='9')  //遇到数字时
            {
                int x=0;
                while(s[i]>='0'&&s[i]<='9')   //先将数字转换为整型
                {
                    x=x*10+(s[i]-'0');
                    i++;
                }
                Push(&s2,x);    //将整型变量放入栈中，用于运算
                printf("%d ",x);
                i--;
            }
            else
            {
                ElemType e;
                if(s[i]!='(') //当你遇到的字符不是"("
                {
                    while(GetTop(&s1,&e)&&f(s[i])<=f(e))  //且运算符优先级小于栈顶元素
                    {
                        if(e!='#')printf("%c ",e);    
                        match(&s2,e);      //执行运算
                        Pop(&s1,&e);      //取出栈顶元素，继续下一次判断
                    }
                }
                Push(&s1,s[i]);   //直到优先级大于栈顶元素，入栈
            }
        }
        int m; 
        GetTop(&s2,&m);   //栈中最后只剩栈底元素"#"和最后一个值，最后一个值就是表达式结果
        printf("\n%d",m);
    }
    return  ERROR;
}

2.3 完整代码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define  ERROR  0
#define  OK  1
typedef  int  ElemType;
typedef  struct  StackNode
{
    ElemType data;
    struct StackNode *next;
}StackNode,*SqStack;
int InitStack(SqStack *s)
{
    (*s)=NULL;
    return OK;
}
int EmptyStack(SqStack *s)
{
    if(*s==NULL) return OK;
    else return ERROR;
}
int Push(SqStack *s,ElemType e)
{
    SqStack p;
    p=(SqStack)malloc(sizeof(StackNode));
    p->data=e;
    p->next=*s;
    *s=p;
    return OK;
}
int Pop(SqStack *s,ElemType *e)
{
    if(*s==NULL) 
         return ERROR;
    else
    {
        SqStack p;
        p=*s;
        *e=p->data;
        *s=(*s)->next;
        free(p);
        return OK;
    }
}
int GetTop(SqStack *s,ElemType *e)
{
    if(*s==NULL) 
        return ERROR;
    else
    {
        *e=(*s)->data;
        return OK;
    }
}
int f(char s2)
{
    if(s2=='#') return -1;
    else if(s2=='(') return 0;
    else if(s2=='+'||s2=='-') return 1;
    else if(s2=='*'||s2=='/') return 2;
}
int match(SqStack *s,char s2)
{
    int a,b;
    ElemType e;
    switch(s2)
    {
        case '+':
            GetTop(s,&b);
            Pop(s,&e);
            GetTop(s,&a);
            Pop(s,&e);
            Push(s,a+b);
            break;
        case '-':
            GetTop(s,&b);
            Pop(s,&e);
            GetTop(s,&a);
            Pop(s,&e);
            Push(s,a-b);
            break;
        case '*':
            GetTop(s,&b);
            Pop(s,&e);
            GetTop(s,&a);
            Pop(s,&e);
            Push(s,a*b);
            break;
        case '/':
            GetTop(s,&b);
            Pop(s,&e);
            GetTop(s,&a);
            Pop(s,&e);
            Push(s,a/b);
            break;
        case '#':break;
    }
}
int  main()
{
 
    char s[100];
    while(gets(s))
    {
        SqStack s1,s2;
        InitStack(&s1);
        InitStack(&s2);
        Push(&s1,'#');
        int i;
        for(i=0;i<strlen(s);i++)
        {
            if(s[i]==')')
            {
                ElemType e;
                while(GetTop(&s1,&e)&&e!='(')
                {
                    printf("%c ",e);
                    match(&s2,e);
                    Pop(&s1,&e);
                }
                Pop(&s1,&e);
            }
            else if(s[i]>='0'&&s[i]<='9')
            {
                int x=0;
                while(s[i]>='0'&&s[i]<='9')
                {
                    x=x*10+(s[i]-'0');
                    i++;
                }
                Push(&s2,x);
                printf("%d ",x);
                i--;
            }
            else
            {
                ElemType e;
                if(s[i]!='(')
                {
                    while(GetTop(&s1,&e)&&f(s[i])<=f(e))
                    {
                        if(e!='#')printf("%c ",e);
                        match(&s2,e);
                        Pop(&s1,&e);
                    }
                }
                Push(&s1,s[i]);
            }
        }
        int m;
        GetTop(&s2,&m);
        printf("\n%d",m);
    }
    return  ERROR;
}

简单表达式的计算（两种方法）

方法一

1.1 后缀式的转换

1.2 计算后缀式

1.3 完整代码

方法二

2.1 计算函数

2.2 主函数

2.3 完整代码

运行结果

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

简单表达式的计算（两种方法）

方法一

1.1 后缀式的转换

1.2 计算后缀式

1.3 完整代码

方法二

2.1 计算函数

2.2 主函数

2.3 完整代码

运行结果

热门文章

最新文章

相关课程

相关电子书

相关实验场景