首页 > 编程语言 >栈和相关算法

栈和相关算法

时间：2024-01-18 18:25:08浏览次数：27  
标签：出栈 return 入栈 int top 算法 相关 expression

栈

栈是一种抽象数据结构（ADT），其主要特性是后进先出LIFO(Last in First out)

  • 实现方式

可以用数组、链表实现，本质就是对一个列表进行后进先出的操作

  • 操作

栈的操作主要有push入栈、pop出栈、isEmpty判空、getTop获取栈顶元素

数组实现

首先进行最基本的数据结构和操作定义：

//栈空条件
top = -1
//栈满条件
top >= MAX - 1

在stack.h头文件中定义栈的结构体和声明一些操作函数。一个栈由存放数据的数组data和栈顶指针top组成

/*stack.h*/
#ifndef __STACK_H__
#define __STACK_H__

#define MAX 10

typedef struct stackNode {
    int data[MAX];
    int top;
}Stack;

int initStack(Stack* S);	//初始化栈
int Push(Stack* S, int value);	//入栈
int Pop(Stack* S);	//出栈
int isEmpty(Stack S);	//判空
int getTop(Stack S);	//获取栈顶元素

#endif
//为了防止重复引用一个头文件，使用预编译宏规范

操作实现代码：

/*stack.c*/
#include <stdio.h>
#include "stack.h"

int initStack(Stack* S) {
    S->top = -1;
    return 1;
}

int isEmpty(Stack S) {
    if(S.top == -1)
    {
        printf("stack is null\n");
        return 1;
    }
    return 0;
}

/*
入栈时判断栈是否已满，由于本次实现栈顶指针指向的是最后一个入栈的元素，因此判断条件为top <= MAX - 1
满足入栈条件时则加入data数组，并top+1
*/
int Push(Stack* S, int value) {
    if(S->top >= MAX - 1)
        return 0;
    S->data[++S->top] = value;

    return 1;
}
/*
出栈时先判断栈是否为空，接着下标减1
*/
int Pop(Stack* S) {
    if(isEmpty(*S))
    {
        printf("stack null\n");
        return 0;
    }
    S->top--;
    return 1;
}

int getTop(Stack S) {
    if(isEmpty(S))
        return 0;
    return S.data[S.top];
}

void Print(Stack S) {
    int i = 0;
    if(isEmpty(S))
    {
        printf("stack null\n");
        return;
    }
    for(;i <= S.top;i++)
        printf("%d\t", S.data[i]);
    printf("\n");
}

//测试代码
int main() {
    Stack S;
    initStack(&S);
    Push(&S, 1);
    Push(&S, 2);
    Push(&S, 3);
    Push(&S, 4);
    Push(&S, 5);
    Push(&S, 6);
    Push(&S, 7);
    Push(&S, 8);
    Push(&S, 9);
    Push(&S, 10);
    Push(&S, 11);

    Print(S);
    printf("%d\n", getTop(S));
    return 0;
}

链表实现

链表实现其实就是单链表的头插法，用head为栈顶指针，出栈和入栈都只需要改变head的指向

栈的一些应用

1.链表的反转

void Reserse(Link head) {
    Link temp = head;
    
    if(!head) return;
    //为了方便演示，直接使用的c++的标准库中的栈定义
    stack<Link> S;
    
    //首先将链表所有节点入栈
    while(temp != NULL) {
        S.push(temp);
        temp = temp->next;
    }
    
    //获取栈顶节点，最后一个入栈的即为新的链表头节点
    temp = S.top();
    S.pop();
    head = temp;	//此时head和temp都指向新链表的第一个节点
    
    while(!S.empty()) {
        //当栈非空时，将temp->next指针指向当前栈顶的节点
        //出栈一次
        //更新temp指针，使其指向刚反转的新节点
        temp->next = S.top();
        S.pop();
        temp = temp->next;
	}
    //最后将最后一个节点的next置为NULL
    temp->next = NULL;
}

表达式计算

1.中缀表达式转后缀表达式

思路：从左到右遍历一次中缀表达式，按下面的算法进行转换，将中缀表达式转换为后缀表达式

算法：

（1）字符为操作数

加入后缀表达式，在这还需加入一些逻辑来获取大于等于10的数字或者小数，比如循环读取连续的数字组成一个完整的数字，然后用空格或其他操作数分隔

（2）字符为左括号

直接入栈

（3）字符为右括号

连续出栈，并将出栈元素加入后缀表达式，直到栈顶元素为左括号，将左括号出栈但不加入后缀表达式

（4）字符为运算符

若栈空，直接入栈。

若栈非空，判断运算符优先级是否高于栈顶运算符，高于则入栈，否则连续出栈，直到该运算符优先级高于栈顶运算符或栈空

（5）遍历完中缀表达式后，还需判断栈是否非空，非空则将全部元素出栈，加入后缀表达式

string InfixToPostfix(string expression) {
    stack<char> S;
    string postfix = "";

    for(int i = 0;i < expression.length();i++) {
        if(expression[i] == ' ' || expression[i] == ',') continue; 
        
        if(IsOperator(expression[i])) { //字符=运算符
            while(!S.empty() && '(' != S.top() && !HigherPrecedence(S.top(), expression[i])) {
                //当栈非空，且操作符优先级未大于栈顶元素时，出栈并加入postfix
                postfix += S.top();
                S.pop();
            }
            S.push(expression[i]);
        }else if(IsOperand(expression[i])) {    //字符=操作数
            while(IsOperand(expression[i])) {
                postfix += expression[i];
                i += 1;
            }
            postfix += ' ';
            i--;
        }else if('(' == expression[i]) {    //字符=左括号
            S.push(expression[i]);
        }else if(')' == expression[i]) {
            while (!S.empty() && S.top() != '(')    //字符=右括号
            {
                postfix += S.top();
                S.pop();
            }
            S.pop();
        }
    }
            //将剩余元素出栈
    while(!S.empty()) {
        postfix += S.top();
        S.pop();
    }
    return postfix;
}

2.后缀表达式计算

算法：

（1）字符为操作数

直接入栈

（2）字符为运算符

连续出栈两次，与运算符进行运算，结果入栈

（3）重复以上步骤直到遍历完后缀表达式

int EvaluetionPostfix(string expression) {
    stack<int> S;

    for(int i = 0;i < expression.length();i++) {
        if(expression[i] == ' ' || expression[i] == ',') continue;

        else if(IsOperator(expression[i])) {    /*字符为运算符*/
            int operand1, operand2, result;
            //出栈两个操作数
            operand1 = S.top(); S.pop();
            operand2 = S.top(); S.pop();
            result = PerformOperation(expression[i], operand1, operand2);
            //结果入栈
            S.push(result);
        } else if(IsNumericDigit(expression[i])) {  /*字符为操作数*/
            int operand = 0;
            //提取操作数的值，考虑超过个位的数值
            while(i < expression.length() && IsNumericDigit(expression[i])) {
                operand = (operand * 10) + (expression[i] - '0');
                i++;
            }
            //避免i++两次导致错误，因此需-1
            i--;
            //将操作数入栈
            S.push(operand);
        }
    }

    return S.top();
}

3.完整代码

#include <iostream>
#include <stack>
#include <string>

using namespace std;

//计算后缀表达式函数
int EvaluetionPostfix(string expression);
//二元表达式计算
int PerformOperation(char operation, int operand1, int operand2);
//中缀转后缀
string InfixToPostfix(string expression);
//运算符判断
bool IsOperator(char c);
//操作数判断
bool IsOperand(char c);
//获取运算符权重
int GetOperatorWeight(char op);
//运算符优先级比较
bool HigherPrecedence(char op1, char op2);

int main() {
    string expression = "";
    cout<<"Input your expression:\n";
    getline(cin, expression);
    int result = EvaluetionPostfix(InfixToPostfix(expression));
    cout<<"Output = "<<result<<"\n";
    cin>>result;
}

int EvaluetionPostfix(string expression) {
    stack<int> S;

    for(int i = 0;i < expression.length();i++) {
        if(expression[i] == ' ' || expression[i] == ',') continue;

        else if(IsOperator(expression[i])) {    /*字符为运算符*/
            int operand1, operand2, result;
            //出栈两个操作数
            operand1 = S.top(); S.pop();
            operand2 = S.top(); S.pop();
            result = PerformOperation(expression[i], operand1, operand2);
            //结果入栈
            S.push(result);
        } else if(IsOperand(expression[i])) {  /*字符为操作数*/
            int operand = 0;
            //提取操作数的值，考虑超过个位的数值
            while(i < expression.length() && IsOperand(expression[i])) {
                operand = (operand * 10) + (expression[i] - '0');
                i++;
            }
            //避免i++两次导致错误，因此需-1
            i--;
            //将操作数入栈
            S.push(operand);
        }
    }

    return S.top();
}

int PerformOperation(char operation, int operand1, int operand2) {
    if (operation == '+') return (operand1 + operand2);
    else if (operation == '-') return (operand1 - operand2);
    else if (operation == '*') return (operand1 * operand2);
    else if (operation == '/') return (operand1 / operand2);
    else {
        cout<<"operation error\n";
        return 0;
    }
}

string InfixToPostfix(string expression) {
    stack<char> S;
    string postfix = "";

    for(int i = 0;i < expression.length();i++) {
        if(expression[i] == ' ' || expression[i] == ',') continue; 
        
        if(IsOperator(expression[i])) { //字符=运算符
            while(!S.empty() && '(' != S.top() && !HigherPrecedence(S.top(), expression[i])) {
                //当栈非空，且操作符优先级未大于栈顶元素时，出栈并加入postfix
                postfix += S.top();
                S.pop();
            }
            S.push(expression[i]);
        }else if(IsOperand(expression[i])) {    //字符=操作数
            while(IsOperand(expression[i])) {
                postfix += expression[i];
                i += 1;
            }
            postfix += ' ';
            i--;
        }else if('(' == expression[i]) {    //字符=左括号
            S.push(expression[i]);
        }else if(')' == expression[i]) {
            while (!S.empty() && S.top() != '(')    //字符=右括号
            {
                postfix += S.top();
                S.pop();
            }
            S.pop();
        }
    }
            //将剩余元素出栈
    while(!S.empty()) {
        postfix += S.top();
        S.pop();
    }
    return postfix;
}

/*
op2 > op1 ? true : false
*/
bool HigherPrecedence(char op1, char op2) {
    int weight1 = GetOperatorWeight(op1);
    int weight2 = GetOperatorWeight(op2);
    if(weight2 > weight1)
        return true;
    return false;
}

int GetOperatorWeight(char op) {
    int weight = -1;
    switch (op)
    {
    case '+':
    case '-':
        weight = 0;
        break;
    case '*':
    case '/':
        weight = 1;
        break;
    default:
        cout<<"Unkown operator\n";
        break;
    }
    return weight;
}

bool IsOperand(char c) {
    if(c > '0' && c < '9')
        return true;
    return false;
}

bool IsOperator(char c) {
    if(c == '+' || c == '-' || c == '*' || c == '/')
        return true;
    return false;
}

标签：出栈,return,入栈,int,top,算法,相关,expression
From： https://www.cnblogs.com/six-years/p/17973138

相关文章

  • 算法学习Day30 n皇后
    Day30n皇后ByHQWQF2024/01/16笔记51.N皇后按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n 个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数n，返回所有不同的 n皇后问题的解决方......
  • 贪心算法题目2-力扣860
    在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任......
  • 贪心算法-题目3力扣53
    给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。输入：nums=[-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1]的和最大，为 6。子数组 是数组中的一个连续部分。解题思路：从投......
  • 玩玩算法题——Episode 3
    Leetcode2171.拿出最少数目的魔法豆（2024-1-18每日一题）StarRating:4.03提示给定一个正整数数组beans，其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中拿出一些豆子（也可以不拿出），使得剩下的非空袋子中（即至少还有一颗魔法豆的袋子）魔法豆的数目相等。一旦把魔......
  • java实现正态分布算法文心一言
    实现正态分布算法文心一言1.了解正态分布在开始实现正态分布算法之前，我们先来了解一下正态分布是什么。正态分布也被称为高斯分布，是一种常见的连续概率分布。它的概率密度函数可以用一个钟形曲线来表示，曲线的中心对应着均值，曲线的宽度对应着标准差。2.实现流程我们要实现的是......
  • 教学相关工具
    从超星导出压缩包提取某些类型文件，如.docx、.doc等文件源码删除无用目录,如android源码中的build、.idea、.gradle等目录源码对文件及目录统一命名源码对实验报告统一打分源码教务系统期末成绩导入源码......
  • 《算法竞赛》07 组合数学
    二项式定理\((a+b)^n=\sum_{i=0}^n\binomnia^ib^{n-i}\)。杨辉三角每个数对应一个组合数。卢卡斯定理\(m\)为质数时\(\binomnm\bmodp=\binom{n\bmodp}{m\bmodp}\cdot\binom{\lfloor\fracnp\rfloor}{\lfloor\fracmp\rfloor}\bmodp\)。有时候结合递归，对\(\binom{......
  • 用余弦相似度修正评分的协同过滤推荐算法
    前言今天读的这篇论文是一篇于2020年6月份发表在计算机工程与科学(ComputerEngineering&Science)上的一篇论文。论文采用评分矩阵的多种维度进行相似度比较以修正不合理评分，再用修正后的评分进行协同过滤推荐。利用MovieLens和BookCrossing数据库进行实验，结果表明：带修正评分......
  • 玩玩算法题——Episode 2
    Leetcode每日一题：最大字符串匹配数目题干如下：给你一个下标从0开始的数组words，数组中包含互不相同的字符串。如果字符串words[i]与字符串words[j]满足以下条件，我们称它们可以匹配：字符串words[i]等于words[j]的反转字符串。0<=i<j<words.length请你返回数组......
  • 贪心算法-题目1力扣455（简单题）
    力扣455，给小朋友发饼干假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j]>=g[i]，我们可以将这个饼干 j 分配......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99