简单表达式的计算(两种方法)

简介: 数据结构中对于栈的运用,最主要的一个例子就是简单表达式的计算了,当你独自将这个程序写出来的时候,这说明你对于栈的运用已经炉火纯青了,下面我将对这个问题做出详细的解答,让我们一起来看看吧

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

目录
相关文章
|
算法
表达式转换-中缀转后缀表达式后计算-数据结构与算法
表达式转换-中缀转后缀表达式后计算-数据结构与算法
418 0
表达式转换-中缀转后缀表达式后计算-数据结构与算法
|
数据库
通用函数和条件表达式
一、通用函数 函数 说明 NVL 语法:NVL(expr1,expr2) 说明:如果expr1为NULL,则该函数显示expr2的值; 例子:SELECT SALARY, NVL(TO_CHAR(COMMISSION_PCT), 0) FROM EMPLO.
1446 0
|
算法
6.解析表达式算法
6.解析表达式算法
139 0
Lambda 表达式型的排序法
int[] arry = {3,9,5,7,64,51,35,94 }; foreach (int i in arry.OrderBy(i => i)) Console.
648 0
|
9月前
|
存储 JavaScript 前端开发
c++lambda函数与表达式
c++lambda函数与表达式
47 1
表达式x=x&(x-1)的作用
表达式"x=x&(x-1)" x = x & (x - 1)含义:这条语句执行一次,就会把x用二进制格式表示时的最右边的一个二进制1变为二进制0,因为x-1会将该位(x用二进制表示时最右边的一个二进制1)变为0; 应用1:把一个整数用二进...
1734 0
|
前端开发
浅聊组合函数
经历过一些列的函数式编程思想的学习总结,一些重要的高阶函数的学习,以及前一段时间关于 RxJS 的学习。
|
机器学习/深度学习 数据处理 索引
函数组合
函数组合
142 0
如何在C#中运行数学表达式字符串
方法1:利用DataTable中的Compute方法 View Code 1 string expression = "1+2*3"; 2 DataTable eval = new DataTable();object result = eval.
1283 0
|
C语言 C++ 人工智能
标准没有规定C/C++表达式求值顺序
对于表达式,标准并没有规定计算顺序,所以下列代码的运行结果存在多样性: #include stdio.h> int main() {         int m = 1; ...
912 0

热门文章

最新文章