【问题描述】
设计一个程序，实现简单整数的四则运算（运算对象不小于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 完整代码

运行结果

热门文章

最新文章

相关课程

相关电子书

相关实验场景