栈的应用——计算器专题

​ 栈的现实应用很多，这里记录下用栈解决四则运算表达式求值的相关题目。

​​ 平常见到的公式如“7+5*4”，称作中缀表达式，因为所有的运算符号都在两数字的中间，而对于计算机来说，中缀表达式是无法直接解析的。针对这个问题，20世纪50年代，波兰逻辑学家 Jan ukasiewicz，创造了一种不需要括号的后缀表达法，称为逆波兰（ Reverse Polish Notation,RPN）表示。这种后缀表示法，是表达式的一种新的显示方式，非常巧妙地解决了程序实现四则运算的难题。

​​ 以“9+（3-1）×3+10÷2”为例，如果要用后缀表示法应该是2：“9 3 1-3 * + 1 0 2 / +”，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。这种表达不适宜人去使用，但是却很适合计算机。

一、中缀表达式转后缀表达式

以上式为例，中缀表达式“9+（3-1）×3+10÷2”转化为后缀表达式“9 3 1 - 3 * + 1 0 2 / +"。

1. 初始化一空栈，用来对符号进出栈使用。

2. 第一个字符是数字9，输出9，后面是符号“+"，进栈。步骤1 2如下图所示

3. 第三个字符是“（”，依然是符号，因其只是左括号，还未配对，故进栈。。

4. 第四个字符是数字3，输出，总表达式为93，接着是“-”，进栈。步骤 3 4如下图所示。

5. 接下来是数字1，输出，总表达式为931，后面是符号“）”，此时，我们需要去匹配此前的“（"，所以栈顶依次出栈，并输出，直到“（”出栈为止。此时左括号上方只有“一”，因此输出“-”。总的输出表达式为931-。。

6. 接着是数字3，输出，总的表达式为931-3.紧接着是符号“×”，因为此时的栈顶符号为“+”号，优先级低于“×”，因此不输出，“*”进栈。步骤5 6如下图所示。

7. 7.之后是符号“+"，此时当前栈顶元素$"*"$"∗"比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为$"9\quad3\quad 1 - 3 * +"$"931−3∗+"。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+"，左图中的栈底（也是栈顶）的“+”是指“9+（3-1）×3+”中的最后一个“+

8. 紧接着数字10，输出，总表达式变为931-3*+10.后是符号“÷”，所以“/”进栈。步骤7 8如下图所示。

9. 最后一个数字2，输出，总的表达式为9 3 1 - 3 * + 1 0 2.如图49-10的左图所示。*

10. 因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 - 3 * + 1 0 2 / +。步骤9 10如下图所示。

​  要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步：

​ ​ 1.将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
​ ​ 2.将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

二、后缀表达式计算

以上式为例,后缀表达式计算的流程如下:

1. 初始化一个空栈。此栈用来对要运算的数字进出使用。
2. 后缀表达式中前三个都是数字，所以9、3、1进栈，如下图所示

3. 接下来是“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈，
4. 接着是数字3进栈，步骤3 4如下图所示。

5. 后面是“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。
6. 下面是“+”，所以栈中6和9出栈，9与6相加，得到15，将15进栈，步骤 5 6如下图所示。

7. 接着是10与2两数字进栈。
8. 接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈，步骤7 8如下图所示。

9. 最后一个是符号“+"，所以15与5出栈并相加，得到20，将20进栈，
10. 结果是20出栈，栈变为空，步骤9 10 如下图所示。

​

三、示例(后续会更新)

1. poj 2694 逆波兰表达式（递归）

描述

逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。

输入

输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。

输出

输出为一行，表达式的值。
可直接用printf("%f\n", v)输出表达式的值v。

样例输入

* + 11.0 12.0 + 24.0 35.0

样例输出

1357.000000

提示

可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。
此题可使用函数递归调用的方法求解

代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

char a[100];
double expression(){
    scanf("%s",a);
    switch (a[0]){
        case '+': return expression()+expression();
        case '-': return expression()-expression();
        case '*': return expression()*expression();
        case '/': return expression()/expression();
        default:  return atof(a);
    }
}

int main(){
    double ans=expression();
    printf("%lf\n", ans);
}

2. LeetCode 面试题 16.26. 计算器

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7

示例 2:

输入: " 3/2 "
输出: 1

示例 3:

输入: " 3+5 / 2 "
输出: 5

说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

因为不用考虑括号，只有乘除法大与加减法的运算逻辑，代码要简洁很多，简洁代码原出处

class Solution {
public:
    int calculate(string s) {
        char op = '+';
        int val;
        istringstream iss(s);
        stack<int> st;

        while(iss>>val){
            if(op=='+'){
                st.push(val);
            }else if(op=='-'){
                st.push(-val);
            }else{
                int val2 = st.top(); st.pop();
                if(op=='*') st.push(val*val2);
                else if(op=='/') st.push(val2/val);
            }
            iss>>op;
        }

        int res = 0;
        while(st.size()){
            res += st.top(); st.pop();
        }
        return res;
    }
};

参考:《大话数据结构》