栈和相关算法
栈栈是一种抽象数据结构（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;
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;
}
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);
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;
}表达式计算
1.中缀表达式转后缀表达式
思路：从左到右遍历一次中缀表达式，按下面的算法进行转换，将中缀表达式转换为后缀表达式
算法：
（1）字符为操作数
加入后缀表达式，在这还需加入一些逻辑来获取大于等于10的数字或者小数，比如循环读取连续的数字组成一个完整的数字，然后用空格或其他操作数分隔
（2）字符为左括号
直接入栈
（3）字符为右括号
连续出栈，并将出栈元素加入后缀表达式，直到栈顶元素为左括号，将左括号出栈但不加入后缀表达式
（4）字符为运算符
若栈空，直接入栈。
若栈非空，判断运算符优先级是否高于栈顶运算符，高于则入栈，否则连续出栈，直到该运算符优先级高于栈顶运算符或栈空
（5）遍历完中缀表达式后，还需判断栈是否非空，非空则将全部元素出栈，加入后缀表达式
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;
}2.后缀表达式计算
算法：
（1）字符为操作数
直接入栈
（2）字符为运算符
连续出栈两次，与运算符进行运算，结果入栈
（3）重复以上步骤直到遍历完后缀表达式
string InfixToPostfix(string expression) {
stack<char> S;
string postfix = "";
for(int i = 0;i < expression.length();i++) {
if(expression == ' ' || expression == ',') continue;
if(IsOperator(expression)) { //字符=运算符
while(!S.empty() && '(' != S.top() && !HigherPrecedence(S.top(), expression)) {
//当栈非空，且操作符优先级未大于栈顶元素时，出栈并加入postfix
postfix += S.top();
S.pop();
}
S.push(expression);
}else if(IsOperand(expression)) { //字符=操作数
while(IsOperand(expression)) {
postfix += expression;
i += 1;
}
postfix += ' ';
i--;
}else if('(' == expression) { //字符=左括号
S.push(expression);
}else if(')' == expression) {
while (!S.empty() && S.top() != '(') //字符=右括号
{
postfix += S.top();
S.pop();
}
S.pop();
}
}
//将剩余元素出栈
while(!S.empty()) {
postfix += S.top();
S.pop();
}
return postfix;
}3.完整代码
#include #include #include 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
页:
[1]