自学内容网 自学内容网

手把手教数据结构与算法:栈的应用(平衡符号和简单计算器)

基本概念

栈的定义

(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。

在这里插入图片描述


栈顶(Top):线性表允许进行插入删除的那一端。
栈底(Bottom):固定的,不允许进行插入和删除的另一端。
空栈:不含任何元素的空表。

栈的特点

栈被称为后进先出(Last In First Out)的线性表,简称LIFO结构,最后压入栈的元素会被最先弹出

栈的常见基本操作

  1. push:将一个元素压入栈顶。
  2. pop:从栈顶弹出一个元素,并返回它。
  3. top:查看栈顶元素,但不移除它。
  4. isEmpty:检查栈是否为空。
  5. size:获取栈中元素的数量。
  6. clear:清空栈,移除所有元素

了解了栈的功能后,让我们自己实现一个栈,完成下面栈的应用:平衡括号,以及实现一个简单计算器 

栈的应用

问题一:平衡符号

题目描述

在实际编程中,我们经常会嵌套使用括号,如“{}”、“[]”、“()”,如果括号太多,可能会出现括号不匹配的情况,比如“(as))”、“{(bcd})”等。现希望你们编写一个程序,判断输入的一段语句中的括号是否匹配。

注:必须使用栈来实现这一功能,栈类用链表或者数组实现。

提示

可定义一个字典dir,用于字符匹配。map是STL的一个关联容器,它提供一对一的hash。第一个可以称为关键字(key),每个关键字只能在map中出现一次;第二个以称为该关键字的值(value)。

输入

输入字符串s,s是由{},[],()以及数字、字母组成的字符串(全都是半角字符)。

输出

若括号使用规范且匹配,输出“1”,否则输出“0”。

样例输入

4Print(abc[0]+’This is a {}’)

样例输出

1

解题思路

  1. 遍历输入字符串:我们从头到尾遍历输入的字符串,每次取出一个字符进行处理

  2. 使用栈来跟踪括号的匹配情况:我们使用栈来存储遇到的左括号,每当遇到一个右括号时,就检查栈顶的左括号是否与之匹配。如果匹配,则继续处理,如果不匹配,则括号不匹配

  3. 处理括号:当我们遇到左括号时,将其压入栈中;当遇到右括号时,检查栈顶的左括号是否与之匹配。如果匹配,则继续处理下一个字符;如果不匹配,则括号不匹配

  4. 检查栈的状态:最后,检查栈是否为空。如果为空,则表示所有左括号都有相应的右括号与之匹配,返回True;如果栈不为空,则表示某些左括号没有相应的右括号与之匹配,返回False

如上图,先将左括号“{”和“(”入栈,当遇到“)”时,弹出栈顶元素“(”,再依次入栈“[”、“(”、“{”,遇到“}”,“)”,“]”,“}”依次弹出栈顶元素进行匹配,最后判断出栈为空,则该括号匹配

代码实现

结点类

结点类包含数据以及next指针,指向下一个结点

struct Node
    {
        char data;
        Node* next;
    };
自定义栈

栈只需要一个栈顶指针head以及size用来记录栈的大小,初始化时将栈顶指针指向空指针,size置为0,析构函数中则清空栈中所有的元素,回收栈空间

class Mystack {
private:
    struct Node
    {
        char data;
        Node* next;
    };

public:
    Node* head; // 栈顶指针
    int size;   // 栈大小

    Mystack()
    {
        head = nullptr;
        size = 0;
    }; // 初始化空间

    ~Mystack()
    {
        Node* q = new Node;
        while (head != nullptr)
        {
            q = head;
            head = head->next;
            delete q;
        }
    } // 回收栈空间
}
push函数

入栈操作,将一个元素压入栈顶,新节点的next指向原栈顶节点,然后更新栈顶指针head,栈的大小size+1

void push(char elem) {
        Node* tmp = new Node();
        tmp->data = elem;
        size = size + 1;
        tmp->next = head;
        head = tmp;
    };
pop函数

出栈操作,删除栈顶节点,释放其内存,更新栈顶指针head,栈大小size-1

void pop() {
        if (head == nullptr) {
            return;
        }
        Node* tmp = head;
        head = head->next;
        delete tmp;
        size = size - 1;
    };
Symbol_matching函数

Symbol_matching函数用于判断输入的字符串中的括号是否匹配

首先定义一个映射表map<char, char> dic,用于存储括号的匹配关系,左括号作为键,右括号作为值,然后遍历字符串的每个字符,如果当前字符是左括号,将其入栈,如果当前字符是右括号,则需进行匹配。每次匹配时,检查栈是否为空,或者栈顶左括号与当前右括号是否匹配,如果不匹配,则返回 false。 如果匹配,则将栈顶左括号出栈。 最后,判断栈是否为空,如果栈为空则表示所有左括号都有相应的右括号与之匹配,返回 true;否则返回 false

bool Symbol_matching(string str) {
    Mystack stack;
    map<char, char> dic = { {'{','}'}, {'[',']'}, {'(',')'} };
    for (char c : str) 
    {
        if (dic.count(c))
        {
            stack.push(c);
        }
        else if (c == '}' || c == ']' || c == ')') 
        {
            if (stack.size == 0 || dic[stack.head->data] != c) {
                return false;
            }
            else {
                stack.pop();
            }
        }
    }
    return stack.size == 0;
}

完整代码

#include <iostream>
#include <string>
#include <map>
using namespace std;

class Mystack {
private:
struct Node
{
char data;
Node* next;
};

public:
Node* head; //栈顶指针 
int size; //栈大小

Mystack()
{
head = nullptr;
size = 0;
}; //初始化空间

~Mystack()
{
Node* q = new Node;
while (head != nullptr)
{
q = head;
head = head->next;
delete q;
}
} //回收栈空间

void push(char elem) {
//请完成入栈函数代码
Node* tmp = new Node();
tmp->data = elem;
size = size + 1;
tmp->next = head;
head = tmp;
};

void pop() {
if (head == nullptr) {
return;
}
//请完成出栈函数代码
Node* tmp =head;
head = head->next;
delete tmp;
size = size - 1;
};

};
bool Symbol_matching(string str) {
Mystack stack;
map<char, char> dic = { {'{','}'}, {'[',']'}, {'(',')'} };
for (char c : str) 
{
if (dic.count(c))
{
stack.push(c);
}
else if (c == '}' || c == ']' || c == ')') 
{
if (stack.size == 0 || dic[stack.head->data] != c) {
return false;
}
else {
stack.pop();
}
}
}
return stack.size == 0;
}

int main() {
string str;
bool R;
getline(cin, str);
R = Symbol_matching(str);
cout << R << endl;
return 0;
}

问题二:简单计算器的实现

在了解问题二的内容之前,我们先来学习一下三种表达式

表达式知识

中缀表达式

        操作符以中缀形式位于运算数中间(如:3+2),是我们日常通用的算术和逻辑公式表示方法。

后缀表达式

        又称逆波兰式(Reverse Polish Notation - RPN),操作符以后缀形式位于两个运算数后(如:3+2的后缀表达形式就是3 2 +)。

前缀表达式

        又称波兰式(Polish Notation),操作符以前缀形式位于两个运算数前(如:3+2的前缀表达形式就是+ 3 2)

中缀表达式转后缀表达式

参考链接:《数据结构》:中缀表达式转后缀表达式 + 后缀表达式的计算-CSDN博客

从左至右依次遍历中缀表达式各个字符(需要准备一个字符栈存储操作符和括号)

1、字符为运算数 :

直接送入后缀表达式(注:需要先分析出完整的运算数)。

2、字符为左括号 :

直接入栈(注:左括号入栈后优先级降至最低)。

3、字符为右括号 :

直接出栈,并将出栈字符依次送入后缀表达式,直到栈顶字符为左括号(左括号也要出栈,但不送入后缀表达式)。

总结:只要满足 栈顶为左括号 即可进行最后一次出栈。

4、字符为操作符 :

若栈空,直接入栈。

若栈非空,判断栈顶操作符,若栈顶操作符优先级低于该操作符,该操作符入栈;否则一直出栈,并将出栈字符依次送入后缀表达式,直到栈空或栈顶操作符优先级低于该操作符,该操作符再入栈。

总结:只要满足 栈空 或者 优先级高于栈顶操作符 即可停止出栈,并将该操作符入栈。

5、重复以上步骤直至遍历完成中缀表达式,接着判断字符栈是否为空,非空则直接出栈,并将出栈字符依次送入后缀表达式。

注:中缀表达式遍历完成,栈中可能还有字符未输出,故需要判断栈空。

简单计算器题目描述

描述

编写程序,输入一个中缀表达式,最长可容纳80个字符。计算的对象为数据类型为int的正整数,能计算加、减、乘、除,允许使用括号改变优先级。

输入

输入一个中缀表达式。(字符串形式,全都是半角符号)

输出

输出中缀表达式的计算结果

样例输入

(2+3)+(2/3)+(2-3)+(2*3)

样例输出

10

解题思路

首先我们需要使用两个栈,一个存放操作数operands,一个存放运算符operators

然后遍历中缀表达式字符串读取每个字符,并结合栈来处理运算符和操作数。

1、如果是数字,则将其转换为整数,并将其压入操作数栈中。

2、如果是左括号 (,则将其压入运算符栈中。 如果是右括号 ),则执行栈内运算直到遇到匹配的左括号 (,并将结果压入操作数栈中。

3、如果是运算符 + - * /,则根据运算符的优先级决定是否进行运算,并将结果压入操作数栈中。

在遍历完所有字符后,如果运算符栈中还有运算符,则依次执行栈内运算,直到栈为空为止。

最后返回操作数栈中的唯一元素,即为中缀表达式的值

代码实现

这里我们#include<stack>,引入stack库,故不需要重新定义结点类以及栈

evaluate函数

我们定义int evaluate(int left, int right, char op) ,用来得到两个数和对应操作符的计算结果并返回

int evaluate(int left, int right, char op) {
    switch (op) {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            return left / right;
        default:
            return 0;
    }
}
precedence函数

然后我们需要定义precedence(char op),用来判断运算符的优先级,若为乘除则返回2(即优先级最高),若为加减则返回1

int precedence(char op) {
    if (op == '*' || op == '/') {
        return 2;
    } else if (op == '+' || op == '-') {
        return 1;
    } else {
        return 0;
    }
}
evaluateExpression函数

准备工作完成后,我们需要自定义evaluateExpression函数用来计算中缀表达式

在函数开始时,创建两个栈,一个用于存放操作数 operands,另一个用于存放运算符 operators

遍历输入的中缀表达式expr中的每个字符。每次处理表达式中的一个字符

1、处理操作数: 如果当前字符是数字,表示操作数,则将其转换为整数并压入操作数栈 operands 中。 如果当前字符是一个多位数,则继续读取后续字符直到遇到非数字字符,将其合并成一个完整的操作数。

2、处理左括号: 如果当前字符是左括号"(",则将其压入运算符栈 operators 中。

3、处理右括号: 如果当前字符是右括号")",则执行栈内运算直到遇到匹配的左括号 (,具体操作是:弹出运算符栈顶的运算符,直到遇到左括号"("。每次弹出运算符时,同时从操作数栈中弹出两个操作数,将它们和运算符进行计算,结果压入操作数栈中。 弹出左括号"(",但不输出到结果。

4、处理运算符: 如果当前字符是运算符 + - * /,则根据其优先级和栈顶运算符的优先级进行比较:如果运算符栈为空,或者当前运算符优先级高于栈顶运算符优先级,则将当前运算符压入运算符栈中。 否则,不断地弹出运算符栈顶运算符直到满足上述条件,并将其压入操作数栈中。

在遍历完所有字符后,如果运算符栈中还有运算符,则依次执行栈内运算,直到栈为空为止

最后返回操作数栈顶的元素,即为中缀表达式的值。

int evaluateExpression(const string& expr) {
    stack<int> operands;
    stack<char> operators;

    for (int i = 0; i < expr.length(); i++) {
        char c = expr[i];

        if (isdigit(c)) {
            int num = c - '0';
            while (i + 1 < expr.length() && isdigit(expr[i + 1])) {
                num = num * 10 + (expr[i + 1] - '0');
                i++;
            }
            operands.push(num);
        } else if (c == '(') {
            operators.push(c);
        } else if (c == ')') {
            while (!operators.empty() && operators.top() != '(') {
                char op = operators.top();
                operators.pop();
                int right = operands.top();
                operands.pop();
                int left = operands.top();
                operands.pop();
                operands.push(evaluate(left, right, op));
            }
            operators.pop();
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!operators.empty() && precedence(operators.top()) >= precedence(c)) {
                char op = operators.top();
                operators.pop();
                int right = operands.top();
                operands.pop();
                int left = operands.top();
                operands.pop();
                operands.push(evaluate(left, right, op));
            }
            operators.push(c);
        }
    }
    while (!operators.empty()) {
    char op = operators.top();
    operators.pop();
    int right = operands.top();
    operands.pop();
    int left = operands.top();
    operands.pop();
    operands.push(evaluate(left, right, op));
}

return operands.top();
}

完整代码

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

using namespace std;

int precedence(char op) {
    if (op == '*' || op == '/') {
        return 2;
    } else if (op == '+' || op == '-') {
        return 1;
    } else {
        return 0;
    }
}

int evaluate(int left, int right, char op) {
    switch (op) {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            return left / right;
        default:
            return 0;
    }
}

int evaluateExpression(const string& expr) {
    stack<int> operands;
    stack<char> operators;

    for (int i = 0; i < expr.length(); i++) {
        char c = expr[i];

        if (isdigit(c)) {
            int num = c - '0';
            while (i + 1 < expr.length() && isdigit(expr[i + 1])) {
                num = num * 10 + (expr[i + 1] - '0');
                i++;
            }
            operands.push(num);
        } else if (c == '(') {
            operators.push(c);
        } else if (c == ')') {
            while (!operators.empty() && operators.top() != '(') {
                char op = operators.top();
                operators.pop();
                int right = operands.top();
                operands.pop();
                int left = operands.top();
                operands.pop();
                operands.push(evaluate(left, right, op));
            }
            operators.pop();
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!operators.empty() && precedence(operators.top()) >= precedence(c)) {
                char op = operators.top();
                operators.pop();
                int right = operands.top();
                operands.pop();
                int left = operands.top();
                operands.pop();
                operands.push(evaluate(left, right, op));
            }
            operators.push(c);
        }
    }
    while (!operators.empty()) {
    char op = operators.top();
    operators.pop();
    int right = operands.top();
    operands.pop();
    int left = operands.top();
    operands.pop();
    operands.push(evaluate(left, right, op));
}

return operands.top();
}

int main() {
string expr;
getline(cin, expr);

int result = evaluateExpression(expr);
cout << result << endl;

return 0;
}

附录

分类专栏

链接:

​​​​​手把手教数据结构与算法

本专栏上一节

链接:

手把手教数据结构与算法:循环单链表设计(约瑟夫问题)-CSDN博客


原文地址:https://blog.csdn.net/weixin_73611714/article/details/138235461

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!