NOIP信奥赛算法之《加减算式》

昨天晚上儿子说要考考我，让我做一道题，输入是一行一句只有加减运算的算式，譬如1+5-7，让我写一个程序来计算出结果。

C++里没有原生支持以字符串形式导入一个表达式，并直接计算出结果的能力，可能有一些第三方的库支持。正常做法，如果表达式里有加减乘除四则运算，还有小括号来强制指定优先级，则先把表达式转换成逆波兰表达式，再计算之。未来我会给出具体解法，难度属于“普及+/提高-”。

而这一题，只有加减两种运算，那就只能算入门难度了。因为加减运算的优先级相同，都按从左至右的结合律依次两两计算。

表达式中有数字，有+和-两种运算符，混合在了一起，显然，用string类型来保存整个表达式最方便。

表达式可能会非常长，譬如下面是一个例子：

每个数字可能都不止一位，因此，要用一个int类型的变量来逐位提取每个参与运算的数字。

自从2021年9月后，C++14新特性终于可以用于NOIP了，语法糖（syntactic sugar，是指编程语言中可以更容易表达一个操作的语法，它可以使程序员更加容易去使用这门语言，操作可以变得更加清晰、方便，或者更加符合程序员的编程习惯）又有增加，对于一个字符串，可以用以下方式来遍历字符串s：

而在这之前，只能用下面的语句来遍历：

而且这种用法还会触发编译器告警，因为如果i为int类型，i的最大上限值是2,147,483,648，如果字符串的长度超过这个值，多余的部分就无法遍历到，正确的写法如下：

这种写法更为冗长，好在有了C++14，不用再那么麻烦了。

除了以上三种之外，还有第四种遍历string的方法，一起来看一下：

以上这种是采用迭代器iterator遍历string的方法。

第一种方法最简洁，但是也有缺陷，譬如无法从右往左遍历字符串，也无法在一次循环中同时获得字符串的多个字符。所以其它几种方法也并不能被方法一完全取代。在某些场合还是得使用如上这些看起来比较复杂的遍历方法。

在循环体内，需要对string中的每一个元素做判断，如果是数字，一种处理方式，否则，就是+或者-，那就是另外一种处理方式。程序结构如下：

在处理字符串中的数字之前，首先要搞清一件事， 形如"12345"和12345，在计算机内是完全不同的两种值，前者是一串字符串，并不能进行数学运算，只能打印出来。而后者是真实的数字，可进行数学运算。同样，字符'3'和数字3也完全是两码事。在C++里，字符串用双引号括起来，字符用单引号括起来。

表达式中夹杂着数字和+和-的运算符。我们只能把表达式当作一串字符来处理。因此我们要想个办法，把表达式中的数字字符串，譬如"12345"转变成12345，好让它进行数学运算。

我用前面的方案一，把表达式字符串s中的每一个字符依次放入字符变量ch里。如果ch连续的得到数字字符，则需要把它们合并成一个int类型的整数，方法是用一个初始值为0的变量，不断的乘以10，再加上这个数字。譬如字符串"123"，从左往右，先把1拿出来，放在某个变量num中，然后乘以10再加上2，得到12放入num中，然后把num再乘以10得到120再加上3，就得到了123。

由于ch虽然看上去是数字，其实本质是一个char类型的字符，要通过减去字符'0'，得到一个真正的数字。字符0~9在ASCII表中是连续排列的，如果我们得到或者保存一个字符'3'，其实它在计算机内真正的值是十进制的51，是该字符的ASCII码值。显然我们不能用51去直接运算。那怎么让51变成数字3呢？只要让它减去'0'的ASCII码值即可。'0'的ASCII码值为十进制48， '3' - '0' = 51 - 48 = 3。这就完成了从'3'到3的转换。

因此对于一连串的数字形式的字符，要转成int类型的整数，可用如下的方式：

接下来，该处理运算符了，如果变量ch遇到一个运算符，该怎么处理？首先，我们可以意识到，遇到运算符就意味着变量num的数字合并工作暂时告一段落，变量num中的数字可以参于运算了，可以用来和上一次运算的结果进行+或者-的运算。那到底是+还是-呢？这可不是由当前的ch中的运算符来决定的，而是由上一次得到的运算符来决定的。因此，要有一个变量，来保存上一次的运算符。给它取个名字叫last_op吧，给其一个初始值+。并用另一个变量ans来保存上一次运算的结果，给一个初始值0。

试想，当遇到表达式中第一个运算符的时候（无论它是+还是-），num中保存的数字立即就会与初始值为0的ans做+的操作，并把结果保存在ans里。这就是我们想要的结果。等运算完成，last_op的使命完成，我们就可以把当前ch中保存的运算符，放入last_op中，用于下一次的计算。同时，还要把num置为0，因为num的当前计算已经完成，它要变成0，以迎接下一批连续的数字。代码可扩展如下：

我们快完成了，但这样的程序还是不太正确，试想一下，所有的表达式是以数字结尾的，并非以+或者-结尾。譬如表达式1 - 3 + 5， 最后，有一个数字5，最后不可能是一个+或者一个-。 而我们的任意一次计算，都是在遇到运算符+或者-时，才进行的。那最后那个数字，保存在num里的最后的数字，似乎是没有机会运行的，因为循环已经结束，它将被悲惨的丢弃掉。解决的办法也比较巧妙，当我们通过命令行得到整个表达式，在开始做计算之前，我们人为在表达式最后添加一个运算符，随便添加一个+或者-，都可以。这个运算符不会参于运算，只是为了让它左侧的那个数字，不被丢弃。

整个程序的完整代码如下：

这道题在洛谷上有，编号是P2788，感兴趣的同学可以去尝试一下。

到这里，这题就做完了。儿子看完后大笑着说，“完全没有必要那么麻烦，看我的”，然后他给出了如下的代码：

这段只有11行的代码，利用了C++中cin语句的一个特性，当输入譬如为1+5-3时，如果用一个整数(int)类型的变量通过循环语句连续不断的去接收它，这个变量会先得到1, 再得到+5， 再得到-3，它会把+号和-号当作该数字的符号位，而不是运算符。如果把得到的这些数字加起来， 就有1 + (+5) + (-3)。其实结果与1+5-3并无不同，因此代码就可以简单到爆了。