NYOJ-35 表达式求值

表达式求值

时间限制：3000ms | 内存限制：65535KB难度：4

描述

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

1 /*
  2    功能Function Description:     利用栈实现中序表达式   NYOJ-35
  3    开发环境Environment:          DEV C++ 4.9.9.1
  4    技术特点Technique:
  5    版本Version:
  6    作者Author:                   可笑痴狂
  7    日期Date:                      20120802
  8    备注Notes:                    
  9         表达式 输入'='结束 支持浮点数
 10     注意：
 11         用exit(0) 提交会显示编译错误，没有<conin.h>头文件 
 12 */
 13 
 14 #include<cstdio>
 15 #include<iostream>
 16 #include<stack>
 17 #include<cctype>
 18 #include<cmath>
 19 //#include<conio.h>    //exit(0);退出程序包含在#include<conio.h>   #include<stdlib.h>
 20 //#include<cstdlib>
 21 using namespace std;
 22 
 23 stack<double> Opnd;        //操作数栈
 24 stack<char> Optr;       //运算符栈
 25 
 26 void Init()         //栈的初始化
 27 {
 28     while(!Opnd.empty())
 29         Opnd.pop();
 30     while(!Optr.empty())
 31         Optr.pop();
 32     Optr.push('=');    //先压入一个结束符‘=’
 33 }
 34 
 35 char Precede(char i,char j)     //判断i和j的优先级
 36 {
 37     switch(i)
 38     {
 39         case '+':
 40         case '-':
 41             if(j=='+'||j=='-'||j==')'||j=='=')
 42                 return '>';
 43             else
 44                 return '<';
 45         case '*':
 46         case '/':
 47             if(j=='(')
 48                 return '<';
 49             else
 50                 return '>';
 51         case '(':
 52             if(j==')')
 53                 return '=';
 54         //    else if(j=='=')
 55         //        exit(0);
 56             else
 57                 return '<';
 58         case ')':
 59         //    if(j=='(')
 60         //        exit(0);
 61         //    else
 62                 return '>';
 63         case '=':
 64             if(j=='=')
 65                 return '=';
 66         //    else if(j==')')
 67         //        exit(0);
 68             else
 69                 return '<';
 70     }
 71 //    exit(0);
 72 }
 73 
 74 double Operate(double a,char i,double b)    //计算
 75 {
 76     switch (i)
 77     {
 78         case '+':
 79             return a+b;
 80         case '-':
 81             return a-b;
 82         case '*':
 83             return a*b;
 84         case '/':
 85             return a/b;
 86     }
 87 }
 88 
 89 int judge(char c)         //判断---如果c为数字则返回1；若为小数点则返回2；如果c为操作符或者结束符则返回0；；
 90 {
 91     if(isdigit(c))
 92         return 1;
 93     else if(c=='.')
 94         return 2;
 95     else
 96         return 0;
 97 }
 98 
 99 double EvaluateExpression(char *p)         
100 {
101     double a,b,temp;
102     int flag;
103     char *st,*end,c,theta;  //定义操作符theta
104     Init();
105     c=*p;
106     while(c!='='||Optr.top()!='=')  //即当操作符栈和当前读入的字符都是‘=’时结束循环
107     {
108         if(isdigit(c))    //isdigit(c) 如果c是数字，则返回true;    isalpha(c) 如果c是字母，则为true；
109         {
110             temp=0;
111             flag=0;
112             for(;judge(c);c=*(++p))        //当不是数字或小数点时结束循环
113             {
114                 if(judge(c)==1)            //说明是数字
115                 {
116                     temp=temp*10+c-'0';
117                     if(c!=0)
118                         end=p;
119                 }
120                 else                   //说明是小数点
121                 {
122                     st=p;        //记录下小数点的位置
123                     end=p;    //记录小数点后最后一个非零数字的位置
124                     flag=1;     //标记有小数点
125                 }
126             }
127             if(flag)           //调整小数点的位置
128                 temp=temp/pow(10,end-st);
129             Opnd.push(temp);        //记录的数字进栈
130         }
131         else
132         {
133             switch(Precede(Optr.top(),c))
134             {
135                 case '<':     //栈顶元素优先权低
136                     Optr.push(c);
137                     c=*(++p);
138                     break;
139                 case '>':     //栈顶元素优先权高---退栈并将运算结果入栈
140                     theta=Optr.top();
141                     Optr.pop();
142                     a=Opnd.top();
143                     Opnd.pop();
144                     b=Opnd.top();
145                     Opnd.pop();
146                     Opnd.push(Operate(b,theta,a));
147                     break;
148                 case '=':     //脱括号并接收下一字符
149                     Optr.pop();
150                     c=*(++p);
151             }
152         }
153     }
154         return Opnd.top();
155 }
156 
157 int main()
158 {
159     int T;
160     char s[1000];
161     scanf("%d",&T);
162     while(T--)
163     {
164         scanf("%s",s);
165         printf("%.2lf\n",EvaluateExpression(s));
166     }
167     return 0;
168 }

/*
   功能Function Description:     利用栈实现中序表达式
   开发环境Environment:          DEV C++ 4.9.9.1
   技术特点Technique:
   版本Version:
   作者Author:                   可笑痴狂
   日期Date:                   20120802
   备注Notes:                 表达式 输入'#'结束 只能处理整数之间的运算 
*/

#include<cstdio>
#include<iostream>
#include<stack>
#include<cctype>
using namespace std;

stack<int> Opnd;        //操作数栈
stack<char> Optr;       //运算符栈

void Init()
{
    while(!Opnd.empty())
        Opnd.pop();
    while(!Optr.empty())
        Optr.pop();
    Optr.push('#');    //将表达式起始符
}

char Precede(char i,char j)
{
    switch(i)
    {
        case '+':
        case '-':
            if(j=='+'||j=='-'||j==')'||j=='#')
                return '>';
            else
                return '<';
        case '*':
        case '/':
            if(j=='(')
                return '<';
            else
                return '>';
        case '(':
            if(j==')')
                return '=';
            else if(j=='#')
                exit(0);
            else
                return '<';
        case ')':
            if(j=='(')
                exit(0);
            else
                return '>';
        case '#':
            if(j=='#')
                return '=';
            else if(j==')')
                exit(0);
            else
                return '<';
    }
    exit(0);
}

int Operate(int a,char i,int b)
{
    switch (i)
    {
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
    }
}

int EvaluateExpression(char *p)
{
    int a,b,temp;
    char c,theta;  //定义操作符theta
    Init();
    c=*p;
    while(c!='#'||Optr.top()!='#')
    {
        if(isdigit(c))    //isdigit(c) 如果c是数字，则返回true;    isalpha(c) 如果c是字母，则为true；
        {
            temp=0;
            for(;isdigit(c);c=*(++p))
                temp=temp*10+(c-'0');
            Opnd.push(temp);    //检测到有运算符，先把记录的数字进栈
        }
        else
        {

            switch(Precede(Optr.top(),c))
            {
                case '<':     //栈顶元素优先权低
                    Optr.push(c);
                    c=*(++p);
                    break;
                case '>':     //栈顶元素优先权高---退栈并将运算结果入栈
                    theta=Optr.top();
                    Optr.pop();
                    a=Opnd.top();
                    Opnd.pop();
                    b=Opnd.top();
                    Opnd.pop();
                    Opnd.push(Operate(b,theta,a));
                    break;
                case '=':     //脱括号并接收下一字符
                    Optr.pop();
                    c=*(++p);
            }
        }
    }
        return Opnd.top();
}

int main()
{
    int T;
    char s[1000];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        printf("%d\n",EvaluateExpression(s));
    }
    return 0;
}

原文链接: https://www.cnblogs.com/dongsheng/archive/2012/08/02/2620832.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍