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

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

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

【问题描述】
设计一个程序，实现简单整数的四则运算（运算对象不小于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小文件上传
以山向海
290 6
工程师阿龙
|
缓存 网络协议 网络架构
Docker 网络 IP 地址冲突，就该这么处理！
Docker 网络 IP 地址冲突，就该这么处理！
工程师阿龙
654 2
赵广陆
|
机器学习/深度学习 安全
深度学习McCulloch-Pitts模型
深度学习McCulloch-Pitts模型
赵广陆
412 0
撷峰
|
机器学习/深度学习 网络协议 异构计算
浅析GPU通信技术（下）-GPUDirect RDMA
目录 浅析GPU通信技术（上）-GPUDirect P2P 浅析GPU通信技术（中）-NVLink 浅析GPU通信技术（下）-GPUDirect RDMA 1. 背景         前两篇文章我们介绍的GPUDirect P2P和NVLink技术可以大大提升GPU服务器单机的GPU通信性...
撷峰
28726 0
土木林森
|
SQL 关系型数据库 MySQL
【超全整理】SQL日期与时间函数大汇总会：MySQL与SQL Server双轨对比教学，助你轻松搞定时间数据处理难题！
【8月更文挑战第31天】本文介绍了在不同SQL数据库系统（如MySQL、SQL Server、Oracle）中常用的日期与时间函数，包括DATE、NOW()、EXTRACT()、DATE_ADD()、TIMESTAMPDIFF()及日期格式化等，并提供了具体示例。通过对比这些函数在各系统中的使用方法，帮助开发者更高效地处理日期时间数据，满足多种应用场景需求。
土木林森
1742 1
HermanYe996
|
Unix Linux 开发工具
linux笔记 diff及patch的制作与使用
这篇文章是关于Linux系统中使用`diff`命令生成补丁文件以及使用`patch`命令应用这些补丁的详细教程和实战案例。
HermanYe996
529 2
linux笔记 diff及patch的制作与使用
html的七十二变
|
移动开发 物联网 API
HTML6的最新消息
截至2023年10月，HTML6 仍处于提议和讨论阶段，尚未正式发布。W3C 和 WHATWG 等组织正不断迭代和改进 HTML 规范，采用“增量更新”策略。HTML6 的潜在新特性包括：改进的语义和结构元素、增强的 Web 组件支持、更强大的 API、多媒体功能升级、更好的可访问性和性能优化，以及对物联网的支持。这些改进将使开发者能够创建更复杂、高性能且符合无障碍标准的网页。然而，HTML 的发展是非线性的，新版本没有明确的发布时间，开发者应关注官方动态获取最新信息。
html的七十二变
811 2
开发V|TG_ch3nguang
|
存储 区块链 数据安全/隐私保护
Uniswap丨justswap丨pancakeswap去中心化薄饼交易所系统开发逻辑分析及源码示例
Uniswap、JustSwap、PancakeSwap均为去中心化交易所，采用自动做市商（AMM）机制。Uniswap基于以太坊，通过Router、Factory和Pair合约实现交易功能；JustSwap基于TRON网络，支持TRC20代币交易，无手续费；PancakeSwap基于Binance Smart Chain，功能类似Uniswap，支持BSC代币交易。
开发V|TG_ch3nguang
338 0
郑小健
|
人工智能 监控 数据挖掘
数字化转型中的项目管理架构：创新与挑战
【8月更文第7天】简述数字化转型对企业的重要性及其对项目管理带来的影响。 - 概述数字化转型下项目管理架构所面临的机遇与挑战。
郑小健
753 0
众所周知
|
消息中间件 监控 测试技术
惊呆了！Python性能测试高手都用这些神器：JMeter+Locust，效率翻倍📈
【9月更文挑战第8天】在软件开发中，性能测试对确保应用稳定性和高效运行至关重要。对于Python开发者而言，选择合适的性能测试工具能显著提升测试效率并精准定位性能瓶颈。本文深入探讨了JMeter和Locust这两款工具的独特优势。JMeter作为跨平台的性能测试工具，支持多种协议，具备高度可定制性和扩展性；而Locust则专为Python应用设计，利用协程实现高并发，提供实时监控和分布式测试功能。两者结合使用，可在实际项目中实现1+1&gt;2的效果，帮助开发者构建全面高效的测试方案，保障应用稳定运行。
众所周知
753 1

热门文章

最新文章

  • 1
    OpenSearch大模型实践之Havenask篇
  • 2
    一文掌握：Gitlab的完整使用手册
  • 3
    java实现图片与base64转换
  • 4
    手机验证码登录
  • 5
    Pycharm2022最新版安装破解与激活教程，亲测可用
  • 6
    Java单元测试之 单元测试规范
  • 7
    Exchange 中关于邮件的生命周期和托管文件夹的相关设定
  • 8
    抽象工厂模式
  • 9
    Android按返回键（后退键）Back键事件捕获的两种方法
  • 10
    Linux下安装显卡Run格式
  • 1
    关于synchronized-reentrantlock-volatile学习总结1.0
    35
  • 2
    最新PyCharm 安装详细图文教程：小白也能轻松搞定
    59
  • 3
    用错工具比没工具更可怕：Ansible vs Terraform 实战对比，用最接地气的方式讲清楚
    46
  • 4
    别等系统报警了才想起 Trace！——分布式事务可观测性的那些坑与优化套路
    54
  • 5
    数据建模到底怎么稳？从维度建模聊到列式存储，让你的数据仓库飞起来！
    41
  • 6
    基于反馈循环的自我进化AI智能体：原理、架构与代码实现
    56
  • 7
    LLM为何难以胜任复杂任务？探索AI认知局限
    51
  • 8
    【Java架构师体系课 | MySQL篇】⑦ 深入理解MySQL事务隔离级别与锁机制
    44
  • 9
    阿里云服务器最便宜多少钱一年？38元一年，配置、价格及购买限制说明
    53
  • 10
    强化网站安全的利器（Nginx中如何正确配置HSTS安全头）
    36

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云负载均衡收费标准：ALB、NLB和CLB价格，包括LCU费用、实例费和公网带宽价格