栈和相关算法
栈
栈是一种抽象数据结构（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;
}
莫愁前路无知己，天下谁人不识君