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

表达式求值

程序员文章站 2022-07-15 16:18:34
...

描述

ACM队的mdd想做一个计算器,但是,他要做的不仅仅是一计算一个A+B的计算器,他想实现随便输入一个表达式都能求出它的值的计算器,现在请你帮助他来实现这个计算器吧。
比如输入:“1+2/4=”,程序就输出1.50(结果保留两位小数)

输入

第一行输入一个整数n,共有n组测试数据(n<10)。
每组测试数据只有一行,是一个长度不超过1000的字符串,表示这个运算式,每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0

输出

每组都输出该组运算式的运算结果,输出结果保留两位小数。

样例输入

2
1.000+2/4=
((1+2)*5+1)/4=

样例输出

1.50
4.00

分析

算法分析:

扫描三遍:第一遍去括号;第二遍算乘除;第三遍算加减。

数据结构:

用数组模拟栈;需要两个栈,一个是 char 型用来存储 符号,另一个是 double 型用来存储数值。

代码

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<stdio.h>
#define N 1000

using namespace std;

string a;
double number[N];
char stacks[N];
double stackn[N];

double change(int s)
{
    int i=s,len=a.length();
    double ans1=0,ans2=0,ans=0;
    while(a[i]>='0'&&a[i]<='9'&&i<len)
    {
        ans1=ans1*10+a[i]-'0';
        i++;
    }
    if(a[i]=='.')
    {
        i++;
        int count=0;
        while(a[i]>='0'&&a[i]<='9'&&i<len)
        {
            count++;
            ans2=ans2*10+a[i]-'0';
            i++;
        }
        ans2=ans2/pow(10,count);
    }
    ans=ans1+ans2;
    return ans;
}

double js(int s1,int e1,int s2,int e2)
{
    int i;
    for(i=s1;i<=e1;i++)
    {
        switch(stacks[i])
        {
            case '*':
            {
                stackn[i-s1+s2+1]=stackn[i-s1+s2]*stackn[i-s1+s2+1];
                stackn[i-s1+s2]=-1000000000;
                continue;
            }
            case '/':
            {
                stackn[i-s1+s2+1]=stackn[i-s1+s2]/stackn[i-s1+s2+1];
                stackn[i-s1+s2]=-1000000000;
            }
        }
    }
    int j1,j2;
    for(i=s1;i<=e1;i++)
    {
        j1=i-s1+s2;
        j2=j1+1;
        switch(stacks[i])
        {
             case '+':
            {
                while(stackn[j2]==-1000000000) j2++;
                stackn[j2]=stackn[j1]+stackn[j2];
                continue;
            }
            case '-':
            {
                while(stackn[j2]==-1000000000) j2++;
                stackn[j2]=stackn[j1]-stackn[j2];
            }
        }
    }
    return stackn[j2];
}

double work()
{
    int topn=-1,tops=-1,len,i;
    for(i=0;i<=a.length()-2;)
    {
        if(a[i]>='0'&&a[i]<='9') 
        {
            stackn[++topn]=change(i);
            while((a[i]>='0'&&a[i]<='9')||(a[i]=='.')&&i<=a.length()-2) i++;
        }
        else if(a[i]=='('||a[i]=='+'||a[i]=='-'||a[i]=='/'||a[i]=='*')
        {
            stacks[++tops]=a[i];
            i++;
        }
        else if(a[i]==')')
        {         
            len=0;
            while(stacks[tops]!='(') 
            {
                tops--;len++;
            }
            topn=topn-len;
            stackn[topn]=js(tops+1,tops+len,topn,topn+len);
            tops--;
            i++;
        }
    }
    if(topn==0)  return stackn[topn];
    else return  js(0,tops,0,topn);
}

int main()
{
    int ntest;
    cin>>ntest;
    while(ntest--)
    {
        cin>>a;
        printf("%.2lf\n",work());
    }
    return 0;
}

测试截图

表达式求值

ac截图

表达式求值

相关标签: acm