HDU 5553 Advanced Calculator 表达式求值

这道题来自HDU 5553/ ICPC2015 合肥现场赛 Advanced Calculator,现场赛无人做(那场1题Cu,2题Ag,4题Au)。截至目前HDU上只有三人过这条。我现在还没有过这条,所以想贴出来我的想法、遇到的一些坑和代码http://paste.ubuntu.com/23275313/,也希望有大神能给我一点测试数据什么的。


这道题就是表达式求值,运算符有+-*/()、=(可以连等)。操作数分为 int 和 double。同时有唯一输出函数 print。通常想到的办法就是逆波兰式。

逆波兰式

基本的逆波兰式

逆波兰式将中缀表达式转换为后缀形式。分为两个部分:构造和执行。

构造

首先需要两个栈,栈 tok 储存后缀表达式结果,栈 ops 用来暂时存放运算符。有下面的规则:

  1. 遇到变量的时候直接入 tok 栈
  2. 遇到运算符比较当前运算符 op 和 ops.top() 运算符的优先级
    如果当前运算符 op 优先级大,则将 op 直接入栈 ops。
    如果当前运算符优先级小于等于则依次弹出 ops 栈中运算符并入 tok 栈,直到栈空。
    上面两个操作实际上类似于单调栈,实际保证了优先级越高的操作符越接近栈的底部。
  3. 当 ops 栈顶是左括号 ( 时候,可以认为左括号优先级最,因此当前运算符 op 可以直接入 ops 栈。在当前符号是右括号 ) 的时候,弹出 ops 运算符中并入表达式栈,直到看到左括号 (

执行

在执行时,我们从 tok 栈的底部向上处理。

https://pastebin.ubuntu.com/p/HK7h47tjNJ/

处理单目运算符

有两个单目运算符正号 + 和负号 -,同时他们也身兼二目运算符加法和减法的作用。为了区别这两个运算符,需要增加 bool Arity2 来记录是否在每个操作符前面出现了操作数。如果出现了,则是二目运算符。
特别地,唯一的函数 print 可以作为一个单目运算符处理。实际上对于逆波兰表达式而言,函数本身就应当作为一个运算符,只是参数数目要以逗号数目确定。

不同数据类型的四则运算

首先是数据的存储,对于运算数存储,一种方法是采用union来合并double和int,同时使用type来记录类型信息,不过这里考虑到可能存在的精度问题,以及将变量和常量统一起来,这里采用string val来记录数据,对于常量val为其字面值,对于变量,val为器变量名,对应值查表slots。对于运算符,直接采用char op存储。同时采用struct Item来把运算数和运算符统一,这样方便统一栈操作。

已知的坑

不同数据类型的连等号

考虑以下代码:

1
2
3
4
int a;
double b;
b = a = 1 + 1.5;
print(b);

结果应该a=2,b=2.000000而不是2.500000。

使用double2string转换丢失精度

在进行计算的时候,采用sprintf和sscanf进行string和valuetype之间的转换。
根据cppreference对sprintf的说明:

Precision specifies the minimum number of digits to appear after the decimal point character. The default precision is 6.
可以发现从string到double必须人为指定一个较长的数精度,这里指定了30位的小数。

It should be noticed that not all C— programs should contain variable statements

变量是可以没有声明的直接引用的,这时候默认变量的值是0。

string::substr

这个错误是经常犯的,substr的第二个参数是长度,而不是结束为止。