手把手教数据结构与算法：栈的应用（平衡符号和简单计算器）

栈

基本概念

栈的定义

栈（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）！