AI 助理
备案控制台
开发者社区 云计算 文章 正文

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

2023-02-01 201
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构中对于栈的运用，最主要的一个例子就是简单表达式的计算了，当你独自将这个程序写出来的时候，这说明你对于栈的运用已经炉火纯青了，下面我将对这个问题做出详细的解答，让我们一起来看看吧

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

Want595
目录
相关文章
以山向海
|
JavaScript 前端开发 Java
oss小文件上传
oss小文件上传
以山向海
214 6
弹性计算-小弹
|
人工智能 缓存 调度
技术改变AI发展：RDMA能优化吗？GDR性能提升方案（GPU底层技术系列二）
随着人工智能（AI）的迅速发展，越来越多的应用需要巨大的GPU计算资源。GPUDirect RDMA 是 Kepler 级 GPU 和 CUDA 5.0 中引入的一项技术，可以让使用pcie标准的gpu和第三方设备进行直接的数据交换，而不涉及CPU。
弹性计算-小弹
137978 6
唐家四少官微
|
存储 NoSQL MongoDB
MongoDB如何创建数据库
MongoDB如何创建数据库
唐家四少官微
393 0
撷峰
|
机器学习/深度学习 网络协议 异构计算
浅析GPU通信技术（下）-GPUDirect RDMA
目录 浅析GPU通信技术（上）-GPUDirect P2P 浅析GPU通信技术（中）-NVLink 浅析GPU通信技术（下）-GPUDirect RDMA 1. 背景         前两篇文章我们介绍的GPUDirect P2P和NVLink技术可以大大提升GPU服务器单机的GPU通信性...
撷峰
28132 0
恬静的小魔龙Unity
|
XML 存储 前端开发
想要制作沙盒游戏？那么这一款插件你一定不能错过(Unity3D)
今天给大家介绍一款简单而又强大的多人沙盒游戏开发插件VOXL。 VOXL是一款简单且易于理解的多重体素沙盒游戏，使用Unity的UNET网络系统开发。 由于服务器和客户端是一体的，所以我们不用再费心搭建服务器，会大大提高我们的开发效率。 VOXL目前只包含大约2500行干净、优雅和易于理解的源代码。
恬静的小魔龙Unity
1049 0
土木林森
|
SQL 关系型数据库 MySQL
【超全整理】SQL日期与时间函数大汇总会：MySQL与SQL Server双轨对比教学，助你轻松搞定时间数据处理难题！
【8月更文挑战第31天】本文介绍了在不同SQL数据库系统（如MySQL、SQL Server、Oracle）中常用的日期与时间函数，包括DATE、NOW()、EXTRACT()、DATE_ADD()、TIMESTAMPDIFF()及日期格式化等，并提供了具体示例。通过对比这些函数在各系统中的使用方法，帮助开发者更高效地处理日期时间数据，满足多种应用场景需求。
土木林森
1486 1
全干程序员demo
|
5月前
|
人工智能 缓存 自然语言处理
保姆级Spring AI 注解式开发教程,你肯定想不到还能这么玩!
这是一份详尽的 Spring AI 注解式开发教程，涵盖从环境配置到高级功能的全流程。Spring AI 是 Spring 框架中的一个模块，支持 NLP、CV 等 AI 任务。通过注解（如自定义 `@AiPrompt`）与 AOP 切面技术，简化了 AI 服务集成，实现业务逻辑与 AI 基础设施解耦。教程包含创建项目、配置文件、流式响应处理、缓存优化及多任务并行执行等内容，助你快速构建高效、可维护的 AI 应用。
全干程序员demo
935 0
HermanYe996
|
Unix Linux 开发工具
linux笔记 diff及patch的制作与使用
这篇文章是关于Linux系统中使用`diff`命令生成补丁文件以及使用`patch`命令应用这些补丁的详细教程和实战案例。
HermanYe996
372 2
linux笔记 diff及patch的制作与使用
2的n次方_
|
存储 算法 Java
【DFS（深度优先搜索）详解】看这一篇就够啦
本文介绍了深度优先搜索（DFS）算法及其应用。DFS从某个顶点出发，深入探索图的每条路径，直到无法前进为止，然后回溯。文章详细解释了DFS的基本思想，并通过示例图展示了其执行过程。此外，文中还探讨了三种枚举方式：指数型枚举、排列型枚举和组合型枚举，并提供了具体的代码实现。最后，文章通过几道练习题帮助读者更好地理解和应用DFS算法。
2的n次方_
8319 19
【DFS（深度优先搜索）详解】看这一篇就够啦
html的七十二变
|
12月前
|
移动开发 物联网 API
HTML6的最新消息
截至2023年10月，HTML6 仍处于提议和讨论阶段，尚未正式发布。W3C 和 WHATWG 等组织正不断迭代和改进 HTML 规范，采用“增量更新”策略。HTML6 的潜在新特性包括：改进的语义和结构元素、增强的 Web 组件支持、更强大的 API、多媒体功能升级、更好的可访问性和性能优化，以及对物联网的支持。这些改进将使开发者能够创建更复杂、高性能且符合无障碍标准的网页。然而，HTML 的发展是非线性的，新版本没有明确的发布时间，开发者应关注官方动态获取最新信息。
html的七十二变
663 2