欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

OJ C++利用栈实现四则运算

程序员文章站 2022-03-27 20:51:29
题目描述输入一行字符串,是包含±*/合法运算的一行字符串,要求解析字符串的值。输入第一行包括一行整数T,表示样例个数。对于每一个样例,输入一行字符串代表合法运算。输出对于每一个样例,输出一个数字表示结果。结果误差要求小于1e-4。样例输入23/4+22+3*4样例输出2.7514思路:用两个栈分别存放浮点型数字和字符型“+、-、*、/”运算符,由于两者数据类型不同,我定义了两种类型的栈,代码量较大,实际上应该可以用模板template实现两个栈共用一个栈模板,从而简化代码。...

题目描述
输入一行字符串,是包含±*/合法运算的一行字符串,要求解析字符串的值。
输入
第一行包括一行整数T,表示样例个数。
对于每一个样例,输入一行字符串代表合法运算。
输出
对于每一个样例,输出一个数字表示结果。结果误差要求小于1e-4。
样例输入

2
3/4+2
2+3*4

样例输出

2.75
14

思路:用两个栈分别存放浮点型数字和字符型“+、-、*、/”运算符,由于两者数据类型不同,我定义了两种类型的栈,代码量较大,实际上应该可以用模板template实现两个栈共用一个栈模板,从而简化代码。
算法:

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define OK 1
#define ERROR 0

typedef char ElemType;
typedef double ElemType2;
typedef bool Status;

typedef struct SNode
{
    ElemType data;
    struct SNode *next;
}SNode,*SLNode;

typedef struct
{
    SLNode top;
    int count;
}SLinkStack;

//Status Init_LStack(SLinkStack *s);//初始化栈
//Status GetTop_LStack(SLinkStack s,ElemType *e);//获取栈顶元素
//Status Push(SLinkStack *s,ElemType e);//在栈顶插入元素
//Status Pop(SLinkStack *s,ElemType *e);//栈顶元素出栈
//Status Out_LStack(SLinkStack s);//输出栈中元素

Status Init_LStack(SLinkStack *s)
{
    s->top=(SLNode)malloc(sizeof(SNode));
    if(!s)
        return ERROR;
    s->top=NULL;
    s->count=0;
    return OK;
}
Status Push(SLinkStack *s,ElemType e)
{
    SLNode p;
    p=(SLNode)malloc(sizeof(SNode));
    if(!p)
       return ERROR;
    p->data=e;
    p->next=s->top;
    s->top=p;
    s->count++;
    return OK;
}
Status Pop(SLinkStack *s,ElemType *e)
{
    SLNode p;
    if(s->top==NULL)
        return ERROR;
    *e=s->top->data;
    p=s->top;
    s->top=p->next;
    free(p);
    s->count--;
    return OK;
}
Status GetTop_LStack(SLinkStack s,ElemType *e)
{
    if(s.top==NULL)
        return ERROR;
    *e=s.top->data;
    return OK;
}
Status Out_LStack(SLinkStack s)
{
    SLNode p;
    p=s.top;
    printf("栈内容为: ");
    while(p)
    {
        printf("%c ",p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}


typedef struct SNode2
{
    ElemType2 data;
    struct SNode2 *next;
}SNode2,*SLNode2;

typedef struct
{
    SLNode2 top;
    int count;
}SLinkStack2;

//Status Init_LStack2(SLinkStack2 *s);//初始化栈
//Status GetTop_LStack2(SLinkStack2 s,ElemType2 *e);//获取栈顶元素
//Status Push2(SLinkStack2 *s,ElemType2 e);//在栈顶插入元素
//Status Pop2(SLinkStack2 *s,ElemType2 *e);//栈顶元素出栈
//Status Out_LStack2(SLinkStack2 s);//输出栈中元素

Status Init_LStack2(SLinkStack2 *s)
{
    s->top=(SLNode2)malloc(sizeof(SNode2));
    if(!s)
        return ERROR;
    s->top=NULL;
    s->count=0;
    return OK;
}
Status Push2(SLinkStack2 *s,ElemType2 e)
{
    SLNode2 p;
    p=(SLNode2)malloc(sizeof(SNode2));
    if(!p)
       return ERROR;
    p->data=e;
    p->next=s->top;
    s->top=p;
    s->count++;
    return OK;
}
Status Pop2(SLinkStack2 *s,ElemType2 *e)
{
    SLNode2 p;
    if(s->top==NULL)
        return ERROR;
    *e=s->top->data;
    p=s->top;
    s->top=p->next;
    free(p);
    s->count--;
    return OK;
}
Status GetTop_LStack2(SLinkStack2 s,ElemType2 *e)
{
    if(s.top==NULL)
        return ERROR;
    *e=s.top->data;
    return OK;
}
Status Out_LStack2(SLinkStack2 s)
{
    SLNode2 p;
    p=s.top;
    printf("栈内容为: ");
    while(p)
    {
        printf("%f ",p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

int main()
{
    int T;string s;double e,e2;char m;
    cin>>T;
    SLinkStack2 S1;SLinkStack S2;
    while(T--)
    {
        Init_LStack2(&S1);Init_LStack(&S2);
        cin>>s;
        for(unsigned int i=0;i<s.length();i++)
        {
            if(s[i]>='0'&&s[i]<='9')
            {
                Push2(&S1,s[i]-'0');
            }
            else
            {
                if(s[i]=='+'||s[i]=='-')
                    Push(&S2,s[i]);
                else
                {
                    Pop2(&S1,&e);
                    if(s[i]=='*')
                        e*=(s[i+1]-'0');
                    else
                        e/=(s[i+1]-'0');
                    i++;
                    Push2(&S1,e);
                }
            }

        }
        while(S1.top!=NULL&&S2.top!=NULL)
        {
            Pop2(&S1,&e2);Pop(&S2,&m);Pop2(&S1,&e);
            if(m=='+')
                e+=e2;
            else
                e-=e2;
            Push2(&S1,e);
        }
        GetTop_LStack2(S1,&e);
        cout<<e<<endl;
    }
}

本文地址:https://blog.csdn.net/T13629119629/article/details/109245773

相关标签: c++ 算法