第2课 栈的应用

表达式问题

中缀表达式

假如要你实现一个可以识别表达式的简易计算器，你会怎么实现？例如用户输入：

3 + 5 * (2 – 4)

可以直接得出计算结果：-7。

对于人类来说，我们很容易计算出来，因为我们从左往右看，看到后面括号时，知道括号内的计算优先级最高，因此可以先计算括号内的，然后反过来计算乘法，最后计算加法，得到最终结果。

对于计算机来说, 比较难计算, 于是有了前缀和后缀表达式.

前缀表达式

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前

比如:

- × + 3 4 5 6

计算思路：

1. 从右至左扫描表达式，遇到数字时，将数字压入堆栈
2. 遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 opt 次顶元素），并将结果入栈
3. 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果.

例如:

- × + 3 4 5 6

• 从右至左扫描，将6、5、4、3 压入堆栈
• 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈
• 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
• 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

后缀表达式

后缀表达式又称逆波兰表达式, 与前缀表达式相似，只是运算符位于操作数之后

比如:

3 4 + 5 × 6 -

计算思路：

与前缀表达式类似，只是顺序是从左至右：

1. 从左至右扫描表达式，遇到数字时，将数字压入堆栈
2. 遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 opt 栈顶元素），并将结果入栈
3. 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如:

3 4 + 5 × 6 -

1. 从左至右扫描，将3和4压入堆栈；
2. 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
3. 将5入栈；
4. 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
5. 将6入栈；
6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

前中后缀表达式的比较

前缀表达式基本没有在商业计算机中使用过，所以现实中用的更多的是后缀表达式。

特性	中缀表达式	前缀表达式	后缀表达式
有无括号	有	无	无
运算方法	回溯	正向枚举	反向枚举
是否使用字符优先级	是	否	否
转换(还原)	栈	树型数据结构	树型数据结构
计算时间	O(n)	O(n)	O(n)
电脑解析难度	高	低	低
别名	中缀记法	波兰表达式	逆波兰表达式

例题 1 P1449 后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

如：3*(5–2)+7对应的后缀表达式为：3．5．2．-*7．+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。

输入格式

输入：后缀表达式

输出格式

输出：表达式的值

输入输出样例

• 输入 #1复制

3.5.2.-*7.+@

• 输出 #1复制

16

说明/提示

字符串长度，1000内。

参考代码 (实现繁琐, 大家可以自行优化下)

#include <bits/stdc++.h>
using namespace std;

stack <int> s;
char str[1008];
char *p, *start, *end;
int a, b;

int main()
{
 scanf("%s", str);
 p = &str[0];

 while(*p != '@') {
  if(*p >= '0' && *p <= '9') {
   start = p;
   while(*p != '.')
    p++;
   *p = '\0';
   a = atoi(start);
   s.push(a);
  }
  else if(*p == '-' ) {
   a = s.top();
   s.pop();
   b = s.top();
   s.pop();
   a = b - a;
   s.push(a);
  }
  else if(*p == '+' ) {
   a = s.top();
   s.pop();
   b = s.top();
   s.pop();
   a = b + a;
   s.push(a);
  }
  else if(*p == '*' ) {
   a = s.top();
   s.pop();
   b = s.top();
   s.pop();
   a = b * a;
   s.push(a);
  }
  else if(*p == '/' ) {
   a = s.top();
   s.pop();
   b = s.top();
   s.pop();
   a = b / a;
   s.push(a);
  }

  p++;
 }

 printf("%d", s.top());

 return 0;
 }

中缀表达式的计算

计算思路：

• 定义两个栈，stack1存储数字，stack2存储运算符
• 将字符串str元素一个个扫描，遇到数字型则进栈stack1
• 遇到运算符型，则要看看栈stack2栈顶元素运算符优先级是否比自己大或等于，如果真比自己大，那么那个运算符出栈，假设出栈是运算符 opt，那么此时从stack1中出栈两个数字x、y参与运算 x opt y，把运算结果进栈stack1
• 此时该运算符还不能进栈，如果栈顶优先级还比自己大或等于，那么那个栈顶运算符还要拿出来运算，直到有小于自己的自己才进栈；
• 遇到 ‘(‘ 直接进stack2
• 遇到 ‘)’，则就要把这一对括号之间运算符都一个个拿出来运算，当str[i]读到’\0’那么扫描结束
• 结束后还要注意stack2里应该还有一个运算符，于是还要多加一步运算，最终stack1中剩一个数，那就是最后结果

例如:

(3+4)x5-6：

1. 建立stack1 操作数, 建立 stack2 存放运算符号
2. 将'(‘ 入栈 stack2
3. 将3入栈stack1
4. 将+号入栈stack2
5. 遇到’)’, 弹出运算符号 + 和 操作数 3 和 4, 做计算 3 + 4 = 7, 将 7 入栈 stack1, 直到遇到'(‘ 后, 将 ‘(‘ 弹出.
6. 遇到 ‘x’ 运算符, 入栈 stack2
7. 将5入栈stack1；
8. 遇到’-‘ 号,比较优先级 stack2 栈顶是 ‘x’，优先级高, 故弹出x号, 弹出5和7，计算出7×5=35，将35入栈 stack1；
9. 将6入栈 stack1；
10. 是’-‘运算符，入栈stack2。
11. 扫描结束后, 依次弹出个运算符号和操作数进行运算. 弹出 -, 弹出 35 和 6, 35 – 6 = 29入栈 stack1.
12. stack2空了之后, stack1的栈顶29就是结果

例题 2 U149191 小西计算器

题目背景

小西花了一天的时间开发了一款强大的整数计算器.

题目描述

小西计算器支持 + – * / 和小括号运算. 运算规则括号优先级最高, 然后乘除, 最后加减. 计算的数值都是正整数在int范围内.

输入格式

计算表达式只有 0-9 的数字, +, -, *, \ 和(), 没有空格. 所有的输入数值都大于 > 0.

输出格式

一个整数 计算结果

输入输出样例

• 输入 #1复制

1+(1+1)*1+(1-1)+1/1-1

• 输出 #1复制

3

说明/提示

表达式长度不超过1000. 所有的数值包括最终结果都在  范围内.

分析

1. 数值读入方式 – 借鉴快读法
2. 中缀表达式求值

参考代码

#include <bits/stdc++.h>
using namespace std;

const int  N = 1000 + 2;
char str[N];
int stack1[N];//存放数字栈
char stack2[N];//存放运算符栈
int top1 = 0,top2 = 0;

int cal_opt(char opt, int x, int y)
{
    switch(opt)
    {
    case '+':
        return (x+y);
    case '-':
        return (x-y);
    case '*':
        return (x*y);
    case '/':
        return (x/y);
    }
}

void cal()
{
 char opt = stack2[top2--]; // 2顶运算符拿出来
    int y = stack1[top1--];//取出一个数字
    int x = stack1[top1--];//再取出一个数字
    stack1[++top1] = cal_opt(opt, x, y);//运算结果要入栈1
    //printf("\n%d%c%d=%d\n", x, opt, y, stack1[top1]);//输出中间运算过程
}

int main()
{
    cin.getline(str, sizeof(str));
 int len = strlen(str);
 int x = 0;
    for(int i = 0; i < len; i++)
    {
     if(str[i] >= '0' && str[i] <= '9') {
      x = x * 10 + (str[i] - '0');
      continue;
  }

  if(x != 0) {
   stack1[++top1] = x;
   x = 0;
  }

        if(str[i] == '+' || str[i] == '-')
        {
            if(top2 == 0)
            {
                stack2[++top2] = str[i];
            }
            else
            {
                while(stack2[top2] == '+' || stack2[top2] == '-' || stack2[top2] == '*' || stack2[top2] == '/')
                {
                    cal();
                }
                stack2[++top2]=str[i];//运算完了之后该运算符要入栈2
            }
        }
        else if(str[i] == '*' || str[i] == '/')//如果str[i]是乘号或除号，则只有栈顶也是乘除号时才需要计算
        {
            if(top2 == 0)//同上
            {
                stack2[++top2]=str[i];
            }
            else
            {
                while(stack2[top2] == '*' || stack2[top2] == '/')
                {
                     cal();
                }
                stack2[++top2]=str[i];//同上
            }
        }

        else if(str[i] == '(')//如果str[i]是左括号则直接压入栈2
        {
            stack2[++top2]=str[i];
        }

        else if(str[i] == ')')//如果str[i]是右括号，则计算第一个左括号前的所有操作符，最后将此左括号直接弹出
        {
            while(stack2[top2] != '(')
            {
                cal();
            }
            stack2[top2--];//弹出
        }
    }

    if(x != 0)
     stack1[++top1] = x;

    while(top2 != 0)
    {
       cal();
    }

    printf("%d\n", stack1[top1]);

    return 0;
}

后缀表达式转换

例题 3 NOIP 2017 第 12 题

表达式 a * (b + c) * d 的后缀形式是（ ）。

 A. a b c d * + *
 B. a b c + * d *
 C. a * b c + * d
 D. b + c * a * d

正确答案：B

后缀构造方式:

• 从左到右依次读取表达式
• 数字时，加入后缀表达式；
• 运算符：
  • 若为 ‘(‘，入栈；
  • 若为 ‘)’，则依次把栈中的运算符加入后缀表达式中，直到出现'(‘，从栈中删除'(‘ ；
  • 若为 除括号外的其他运算符， 当其优先级高于除'(‘以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级 「高和相等」 的运算符，直到一个比它优先级低的或者遇到了一个左括号为止，然后将其自身压入栈中（先出后入）。
• 当扫描的中缀表达式结束时，栈中的的所有运算符依次出栈；

做题示例:

1. 建立空栈存放操作符
2. 从左到右依次读取表达式, 非操作符直接输出, 输出a
3.  号 栈顶入栈
4.  直接入栈
5.  直接输出
6.  号 入栈
7.  直接输出
8.  括号, 完成配对,  弹出 , 弹出 , 输出
9.  号 和栈顶优先级相同, 故栈顶的  出栈
10.  号入栈
11.  直接输出
12. 表达式读取完毕, 栈依次弹出

最后输出结果:  a b c + * d *

例题 4 P1175 表达式的转换

题目描述

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而中缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：8-(3+26)/5+4可以写为：8 3 2 6+5/-4+

其计算步骤为：

8 3 2 6 * + 5 / – 4 + 8 3 12 + 5 / – 4 + 8 15 5 / – 4 + 8 3 – 4 + 5 4 + 9

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

输入格式

就一行，是一个中缀表达式。输入的符号中只有这些基本符号0123456789+-/^()，并且不会出现形如2-3的格式。

表达式中的基本数字也都是一位的，不会出现形如12形式的数字。

所输入的字符串不要判错。

输出格式

若干个后缀表达式，第I+1行比第I行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。

输入输出样例

• 输入 #1复制

8-(3+2*6)/5+4

• 输出 #1复制

8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9

说明/提示

运算的结果可能为负数，/ 以整除运算。并且中间每一步都不会超过  。字符串长度不超过100

分析

两个难点:

1. 后缀表达式的转换
2. 计算过程中的输出

参考代码

#include<bits/stdc++.h>
using namespace std;

const int N = 10000 + 8;
char s[N], hs[N], opt[N];
int num[N], hi, oi, ni, p;

int pri(char ch)
{
 if(ch == '+' || ch == '-') return 1;
 if(ch == '*' || ch == '/') return 2;
 if(ch == '^') return 3;
 return 0;
}

void postfix(char s[])
{
 int len = strlen(s);

 for(int i = 0; i < len; i++) {
  if(s[i] >= '0' && s[i] <= '9') {
   hs[++hi] = s[i];
   continue;
  }

  char op = s[i];
  if(op == '(')
  {
   opt[++oi] = op;
   continue;
  }
  if(op == ')')
  {
   while(opt[oi] != '(')
   {
    hs[++hi] = opt[oi--];
   }
   oi--;
   continue;
  }

  if(pri(opt[oi]) < pri(op))
  {
   opt[++oi] = op;
   continue;
  }

  while(pri(opt[oi]) >= pri(op))
  {
   hs[++hi] = opt[oi--];
  }
  opt[++oi] = op;
 }

 while(oi) {
  hs[++hi] = opt[oi--];
 }
}

void print()
{
 for(int i = 1; i<= ni; i++)
 {
  cout << num[i] <<" ";
 }
 for(int i = p + 1; i<= hi; i++)
 {
  cout << hs[i] << " ";
 }
 cout<<endl;
}

int main()
{
 cin >> s;

 postfix(s);

 print();

 for(int i = 1; i <= hi; i++)
 {
  p=i;
  if(hs[i] >= '0' && hs[i] <= '9')
  {
   num[++ni]= hs[i] - '0';
   continue;
  }

  int y = num[ni--], x = num[ni--];
  int ans;
  switch(hs[i]) {
  case '+':
   ans = x + y;
   break;
  case '-':
   ans = x - y;
   break;
  case '*':
   ans = x * y;
   break;
  case '/':
   ans = x / y;
   break;
  case '^':
   ans = pow(x, y);
   break;
  }

  num[++ni] = ans;
  print();
 }

 return 0;
}

题单

1. P1981 表达式求值
2. P1449 后缀表达式
3. P1175 表达式的转换
4. UVA442 矩阵链乘 Matrix Chain Multiplication
5. U149191 小西计算器