计算后缀表达式-算法与数据结构-栈的运用-C++语言实现

简介: 计算后缀表达式-算法与数据结构-栈的运用-C++语言实现

后缀表达式


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

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

后缀表达式的一个特点就是方便计算。

我们下面只考虑 加减乘除 四种基本运算,以及表达式中没有 负数 的情况。


问题分析

那么我们如何计算一个后缀表达式呢?

可以借用栈来实现。

此外,后缀表达式也可以用一个二叉树来表示和计算,但是我们这里就不细讲啦!


思路

我们先抛开问题中一些具体的细节(如:是用‘.’作为操作数的结束符号),方便理清对于整个问题的一个思路。

还是用之前那个例子:

3.5.2.-*7.+@

我们从后缀表达式左边开始一边读取数据一边压入栈中,当遇到了运算符时,就将栈中的操作符以及紧邻的两个操作数出栈进行相应的运算,运算结果压入栈中作为新的操作数,然后继续从表达式中读取数据。反复进行以上操作直到得到运算结果。

过程如下图:


image.png

一些细节和问题

在了解了一个大概的思路之后,我们就需要考虑程序实现中的一些细节问题了。


一、数据类型处理


一个后缀表达式中有操作数这样的数字,也有运算符这样的符号,所以最终是以博主都用char类型进行存储的。

那么我们如何从以char类型存储了部分表达式的栈中,将操作数和运输符分别读取出来进行运算呢?

需要注意,我们在压入栈中时,是一个字符一个字符的压的,所以在栈中的多位数是倒过来的,如:123压入栈中从栈顶开始看就是321。

下面是从栈中读取出一个操作数的代码段:


//从char型栈中读取出一个int型操作数 
int get_num() {
  int sum(0);
  for(int i = 1; s.top() != '.'; i *= 10) {
  sum += (int)(s.top() - '0') * i;
  s.pop();
  if(s.empty()) break;
  }
  return sum;
}

二、负数


虽然我们前面说了不考虑表达式中有负数的情况,但是在对表达式的计算过程中仍然可能会产生负数,不过这种情况对于博主来说稍稍好处理一点(读取表达式时,负数的负号与减法运算符相同,有歧义)。

博主处理运算过程中负数的方法是,先压入一个字符0作为符号标记,然后将原数的相反数(就是一个非负数了)压入栈中。在出栈时如果数字串的最后一个是0,就将数据取相反数,重新得到原来的负数。


最终代码

#include<iostream>
#include<stack>
using namespace std;
stack<char> s;
int get_num();  //从栈中返回一个整型数字 
int main(){
  char t(0);
  while(true) {
  //输入 
  cin >> t;
  if(t == '@') {
    s.pop();
    cout << get_num();
    break;
  }
  s.push(t);
  //见运算符
  if(t == '+' || t == '-' || t == '*' || t == '/') {
    //出栈运算符
    s.pop();
    //出栈两个数字为int型
    int a(0), b(0);
    s.pop();
    a = get_num();
//    cout << "a = " << a << endl;
    s.pop();
    b = get_num();
//    cout << "b = " << b << endl;
    //计算 
    int result(0);
    if(t == '+') result = b + a;
    else if(t == '-') result = b - a;
    else if(t == '*') result = b * a;
    else if(t == '/') result = b / a;
//    cout << "result = " << result << endl;
    if(result < 0) {
    s.push('0'); 
    result = -result;
//    cout << "result = " << result << endl;
    }
    //结果转为char型再入栈
    stack<char> c;
    if(result == 0) {
    s.push('0');
    }
    while(result != 0) {
    c.push((char)(result % 10 + '0'));
    result /= 10;
    }
    while(!c.empty()) {
    s.push(c.top());
    c.pop();
    }
    s.push('.');
  }
  }
}
//------------------------------
//从char型栈中读取出一个int型操作数 
int get_num() {
  int sum(0);
  char t(0);
  for(int i = 1; s.top() != '.'; i *= 10) {
  t = s.top();
  sum += (int)(s.top() - '0') * i;
  s.pop();
  if(s.empty()) break;
  }
  if(t == '0') sum = -sum;
  return sum;
}
/*
测试数据
3.5.2.-*7.+@
10.28.30./*7.-6.+@
1000.1000./5.-6.*@
*/

总结


后缀表达式是一个比较经典的问题。栈的原理其实很简单,就像一个加了限制的数组,只能从同一端进出数据。

但是在用栈解决一些问题时,你会发现它真的好神奇,也许这就是数据结构和算法的魅力吧!

相关文章
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
92 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
存储 分布式计算 算法
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
72 0
|
2月前
|
算法 C++
2022年第十三届蓝桥杯大赛C/C++语言B组省赛题解
2022年第十三届蓝桥杯大赛C/C++语言B组省赛题解
51 5
|
2月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
74 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
2月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
649 0
高精度算法(加、减、乘、除,使用c++实现)
|
2月前
|
存储 编译器 C语言
深入计算机语言之C++:类与对象(上)
深入计算机语言之C++:类与对象(上)
|
2月前
|
存储 分布式计算 编译器
深入计算机语言之C++:C到C++的过度-2
深入计算机语言之C++:C到C++的过度-2
|
2月前
|
编译器 Linux C语言
深入计算机语言之C++:C到C++的过度-1
深入计算机语言之C++:C到C++的过度-1
|
2月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
2月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
下一篇
DataWorks