在上一次的学习中，使用指针实现了链栈 使用 C++ 实现链栈，接下来学一下顺序栈的实现。
回顾一下栈的概念：
栈是只允许在一端（即栈顶）进行插入或删除操作的线性表，属于逻辑结构。
回顾一下栈的数学性质：
n 个不同元素进栈，出栈元素不同排列的个数为 Catalan （卡特兰）数，即 1 n + 1 C 2 n n \frac{1}{n+1}C^{n}_{2n} n+11C2nn
顺序栈是通过顺序表实现的，是用一组 地址连续 的存储单元依次存储数据元素，简单理解就是用数组来存储的。
顺序栈和顺序表共同的特点为：逻辑上相邻的元素在物理位置上也相邻，即逻辑顺序和物理顺序相同。
接下来是一个最简单的顺序栈的代码实现
#define MaxSize 10004
// 不带头结点的顺序栈
typedef struct {
int data[MaxSize];
int top;
}SeqStack;
// 创建顺序栈
SeqStack createStack(){
SeqStack S;
S.top = -1;
return S;
}
// 判断栈是否为空
bool StackEmpty(SeqStack S){
return S.top == -1;
}
// 入栈
bool Push(SeqStack &S, int x){
if(S.top == MaxSize - 1) { // 栈满报错
return false;
} else {
S.data[++S.top] = x;
return true;
}
}
// 出栈
bool Pop(SeqStack &S, int &x){
if(StackEmpty(S)) {
return false; // 当为空栈时直接返回
} else {
x = S.data[S.top--];
return true;
}
}
接下来我们通过一个题目 剑指 Offer II 036. 后缀表达式 来验证自己实现的顺序栈的正确性。
在做提前我们有必要了解一下后缀表达式，相应的还有前缀、中缀表达式。
中缀表达式是一个通用的算术或逻辑公式表示方法，我们平时用的就是中缀表达式，例如，
(1+1) * 2，结果为4，这种表达式可以轻松用肉眼计算。
特点：除了括号限制运算优先性以外，运算符左右都为运算数
前缀表达式又称波兰表达式，是由一位波兰的数学家提出的，用于简化命题逻辑的一种表达式表示方式。例如
(1+1) * 2的中缀转为前缀表达式为：* + 1 1 2
特点：不含括号就能表示运算优先性，运算符在两个运算数的前面
后缀表达式又称逆波兰表达式，例如
(1+1) * 2的中缀转为后缀表达式为：1 1 + 2 *
特点：不含括号就能表示运算优先性，运算符在两个运算数的后面
在考研考题中经常会考察使用栈来实现表达式的转换，这里主要了解后缀表达式。
记录一下中缀转为前缀和后缀的要点：
左优先原则：只要左边运算符能先计算，就优先计算左边的。
例： 1+(1*2*3)，转为后缀为， 1 1 2 * 3 * +，这里注意到先计算的是 (1*2*3) ，不过是先计算1 * 2 ，即 1 2 * ，然后在将这个结果视为一个数继续与 * 3 进行计算。
右优先原则：只要右边的运算符能先计算就先计算右边的。
例： 1+(1*2*3)，转为前缀为， + 1 * 1 * 2 3
后缀表达式特点：运算符在操作数的后面，于是当我们遇到运算符时，直接往前面找操作数进行运算即可。只需要用一个栈来存储操作数。
设存储操作数的栈为 S S S，栈含有基本操作函数： P u s h Push Push 入栈 ， P o p Pop Pop 出栈
算法实现：
注意点：
在提交代码到 剑指 Offer II 036. 后缀表达式 前，先写一下完整的代码，包括输入输出。
//
// Created by uni1024 on 2022/10/8.
//
#include <cstdlib>
#include <iostream>
#define MaxSize 10004
// 不带头结点的顺序栈
typedef struct {
int data[MaxSize];
int top;
}SeqStack;
// 创建顺序栈
SeqStack createStack(){
SeqStack S;
S.top = -1;
return S;
}
// 判断栈是否为空
bool StackEmpty(SeqStack S){
return S.top == -1;
}
// 入栈
bool Push(SeqStack &S, int x){
if(S.top == MaxSize - 1) { // 栈满报错
return false;
} else {
S.data[++S.top] = x;
return true;
}
}
// 出栈
bool Pop(SeqStack &S, int &x){
if(StackEmpty(S)) {
return false; // 当为空栈时直接返回
} else {
x = S.data[S.top--];
return true;
}
}
// 辅助函数, 判断字符串s的第i个元素是否为数字
bool isDigit(char *s, int i){
return s[i] >= '0' && s[i] <= '9';
}
// 辅助函数, 将数字字符串转为数字, 直到遇到空格
bool getNum(char *s, int &i, int &x){
if(isDigit(s,i)){ // 若当前字符为数字则开始运算
// 判断数字的正负
int flag;
if(i >= 1 && s[i-1] == '-')
flag = -1;
else
flag = 1;
int num = s[i++] - '0';
while(isDigit(s, i)){ // 记录连续的数字
num = num * 10 + s[i++] - '0';
}
x = num * flag; // 记录最终结果
return true;
}
else return false;
}
int main(){
printf("开始程序,请输入一个标准的后缀表达式(用空格隔开):\n");
char s[MaxSize * 10];
gets(s);
printf("获取到的后缀表达式为:%s\n", s);
// 核心算法
SeqStack S = createStack(); // 初始化栈
int i = 0; // 记录当前遍历的位置
int x; // 临时变量
int a, b; // 临时变量
while(s[i] != '\0'){
// 跳过空格字符
if(s[i] == ' ') { i++ ; continue;}
// 1. 当遇到数字时候直接入栈
if(isDigit(s, i)){
getNum(s, i, x);
Push(S, x);
} else {
// 跳过数字负号的情况(因计算数字时会判断正负性）
if(s[i] == '-' && isDigit(s, i+1)) {
i++;
continue;
}
// 其他情况
if(Pop(S, b) && Pop(S, a)){
// 计算后继续入栈
switch (s[i]) {
case '+': Push(S, a + b);break;
case '-': Push(S, a - b); break;
case '*': Push(S, a * b); break;
case '/': Push(S, a / b); break;
default : break;
}
}
}
i ++ ; // 继续遍历下一个字符
}
Pop(S, x);
printf("运算结果: %d\n",x);
return 0;
}
测试数据与结果：
开始程序,请输入一个标准的后缀表达式(用空格隔开):
4 13 5 / +
获取到的后缀表达式为:4 13 5 / +
运算结果: 6
剑指 Offer II 036. 后缀表达式
由于C语言不支持 bool 类型以及 函数中使用&引用参数的地址，这里则提交的是 C++的代码，这里用到了 C++ 的 vector 的遍历，通过使用 for(auto 循环变量:Vector容器变量) 的方式，了解即可。其中辅助函数与之前写的稍有不同，因为这个题目给的输入数据是二维的，相对来说难度就小了一些。
#include <cstdlib>
#include <iostream>
#define MaxSize 10004
// 不带头结点的顺序栈
typedef struct {
int data[MaxSize];
int top;
}SeqStack;
// 创建顺序栈
SeqStack createStack(){
SeqStack S;
S.top = -1;
return S;
}
// 判断栈是否为空
bool StackEmpty(SeqStack S){
return S.top == -1;
}
// 入栈
bool Push(SeqStack &S, int x){
if(S.top == MaxSize - 1) { // 栈满报错
return false;
} else {
S.data[++S.top] = x;
return true;
}
}
// 出栈
bool Pop(SeqStack &S, int &x){
if(StackEmpty(S)) {
return false; // 当为空栈时直接返回
} else {
x = S.data[S.top--];
return true;
}
}
// 辅助函数, 判断字符串s的第i个元素是否为数字
bool isDigit(string s, int i){
return s[i] >= '0' && s[i] <= '9';
}
// 辅助函数, 将数字字符串转为数字, 直到遇到空格
int getNum(string s){
int i = 0;
int flag = 1; // 判断数字的正负
if(s[0] == '-') { flag = -1; i = 1; }
int num = s[i++] - '0';
while(s[i] != '\0' && isDigit(s, i)){ // 记录连续的数字
num = num * 10 + (s[i++] - '0');
}
return num * flag;
}
class Solution {
public:
int evalRPN(vector<string>& tokens) {
SeqStack S = createStack(); // 初始化栈
int x; // 临时变量
int a, b; // 临时变量
// 遍历字符串
for(auto s : tokens){
if(isDigit(s, 0) || isDigit(s, 1)){ // 情况1: 操作数
Push(S, getNum(s));
} else { // 情况2: 运算符
char ch = s[0];
if(Pop(S, b) && Pop(S, a)){
// 计算后继续入栈
switch (ch) {
case '+': Push(S, a + b); break;
case '-': Push(S, a - b); break;
case '*': Push(S, a * b); break;
case '/': Push(S, a / b); break;
default : break;
}
}
}
}
// 取出最终结果
Pop(S, x);
return x;
}
};
提交结果：
