栈和相关算法

栈

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

• 实现方式
  

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

• 操作
  

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

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

1. //栈空条件
2. top = -1
3. //栈满条件
4. top >= MAX - 1

复制代码

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

1. /*stack.h*/
2. #ifndef __STACK_H__
3. #define __STACK_H__
5. #define MAX 10
7. typedef struct stackNode {
8.     int data[MAX];
9.     int top;
10. }Stack;
12. int initStack(Stack* S);        //初始化栈
13. int Push(Stack* S, int value);        //入栈
14. int Pop(Stack* S);        //出栈
15. int isEmpty(Stack S);        //判空
16. int getTop(Stack S);        //获取栈顶元素
18. #endif
19. //为了防止重复引用一个头文件，使用预编译宏规范

复制代码

操作实现代码：

1. /*stack.c*/
2. #include <stdio.h>
3. #include "stack.h"
5. int initStack(Stack* S) {
6.     S->top = -1;
7.     return 1;
8. }
10. int isEmpty(Stack S) {
11.     if(S.top == -1)
12.     {
13.         printf("stack is null\n");
14.         return 1;
15.     }
16.     return 0;
17. }
19. /*
20. 入栈时判断栈是否已满，由于本次实现栈顶指针指向的是最后一个入栈的元素，因此判断条件为top <= MAX - 1
21. 满足入栈条件时则加入data数组，并top+1
22. */
23. int Push(Stack* S, int value) {
24.     if(S->top >= MAX - 1)
25.         return 0;
26.     S->data[++S->top] = value;
28.     return 1;
29. }
30. /*
31. 出栈时先判断栈是否为空，接着下标减1
32. */
33. int Pop(Stack* S) {
34.     if(isEmpty(*S))
35.     {
36.         printf("stack null\n");
37.         return 0;
38.     }
39.     S->top--;
40.     return 1;
41. }
43. int getTop(Stack S) {
44.     if(isEmpty(S))
45.         return 0;
46.     return S.data[S.top];
47. }
49. void Print(Stack S) {
50.     int i = 0;
51.     if(isEmpty(S))
52.     {
53.         printf("stack null\n");
54.         return;
55.     }
56.     for(;i <= S.top;i++)
57.         printf("%d\t", S.data[i]);
58.     printf("\n");
59. }
61. //测试代码
62. int main() {
63.     Stack S;
64.     initStack(&S);
65.     Push(&S, 1);
66.     Push(&S, 2);
67.     Push(&S, 3);
68.     Push(&S, 4);
69.     Push(&S, 5);
70.     Push(&S, 6);
71.     Push(&S, 7);
72.     Push(&S, 8);
73.     Push(&S, 9);
74.     Push(&S, 10);
75.     Push(&S, 11);
77.     Print(S);
78.     printf("%d\n", getTop(S));
79.     return 0;
80. }

复制代码

表达式计算

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

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

算法：
（1）字符为操作数
加入后缀表达式，在这还需加入一些逻辑来获取大于等于10的数字或者小数，比如循环读取连续的数字组成一个完整的数字，然后用空格或其他操作数分隔
（2）字符为左括号
直接入栈
（3）字符为右括号
连续出栈，并将出栈元素加入后缀表达式，直到栈顶元素为左括号，将左括号出栈但不加入后缀表达式
（4）字符为运算符
若栈空，直接入栈。
若栈非空，判断运算符优先级是否高于栈顶运算符，高于则入栈，否则连续出栈，直到该运算符优先级高于栈顶运算符或栈空
（5）遍历完中缀表达式后，还需判断栈是否非空，非空则将全部元素出栈，加入后缀表达式

1. void Reserse(Link head) {
2.     Link temp = head;
3.    
4.     if(!head) return;
5.     //为了方便演示，直接使用的c++的标准库中的栈定义
6.     stack<Link> S;
7.    
8.     //首先将链表所有节点入栈
9.     while(temp != NULL) {
10.         S.push(temp);
11.         temp = temp->next;
12.     }
13.    
14.     //获取栈顶节点，最后一个入栈的即为新的链表头节点
15.     temp = S.top();
16.     S.pop();
17.     head = temp;        //此时head和temp都指向新链表的第一个节点
18.    
19.     while(!S.empty()) {
20.         //当栈非空时，将temp->next指针指向当前栈顶的节点
21.         //出栈一次
22.         //更新temp指针，使其指向刚反转的新节点
23.         temp->next = S.top();
24.         S.pop();
25.         temp = temp->next;
26.         }
27.     //最后将最后一个节点的next置为NULL
28.     temp->next = NULL;
29. }

复制代码

2.后缀表达式计算

算法：
（1）字符为操作数
直接入栈
（2）字符为运算符
连续出栈两次，与运算符进行运算，结果入栈
（3）重复以上步骤直到遍历完后缀表达式

1. string InfixToPostfix(string expression) {
2.     stack<char> S;
3.     string postfix = "";
5.     for(int i = 0;i < expression.length();i++) {
6.         if(expression[i] == ' ' || expression[i] == ',') continue;
7.         
8.         if(IsOperator(expression[i])) { //字符=运算符
9.             while(!S.empty() && '(' != S.top() && !HigherPrecedence(S.top(), expression[i])) {
10.                 //当栈非空，且操作符优先级未大于栈顶元素时，出栈并加入postfix
11.                 postfix += S.top();
12.                 S.pop();
13.             }
14.             S.push(expression[i]);
15.         }else if(IsOperand(expression[i])) {    //字符=操作数
16.             while(IsOperand(expression[i])) {
17.                 postfix += expression[i];
18.                 i += 1;
19.             }
20.             postfix += ' ';
21.             i--;
22.         }else if('(' == expression[i]) {    //字符=左括号
23.             S.push(expression[i]);
24.         }else if(')' == expression[i]) {
25.             while (!S.empty() && S.top() != '(')    //字符=右括号
26.             {
27.                 postfix += S.top();
28.                 S.pop();
29.             }
30.             S.pop();
31.         }
32.     }
33.             //将剩余元素出栈
34.     while(!S.empty()) {
35.         postfix += S.top();
36.         S.pop();
37.     }
38.     return postfix;
39. }

复制代码

3.完整代码

[code]#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