北京林業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二基于棧的算術(shù)表達(dá)式求值算法

這篇具有很好參考價(jià)值的文章主要介紹了北京林業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二基于棧的算術(shù)表達(dá)式求值算法。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

第1關(guān)：基于棧的中綴算術(shù)表達(dá)式求值

參見課本P75 例3.3

#include <iostream>
#include<iomanip>

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct {//運(yùn)算符棧
    char *base;
    char *top;
    int stacksize;
} SqStack1;

Status InitStack1(SqStack1 &S) {//運(yùn)算符棧初始化
    S.base = new char[MAXSIZE];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

Status Push1(SqStack1 &S, char e) {//運(yùn)算符棧入棧
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top = e;
    S.top++;
    return OK;

}

Status Pop1(SqStack1 &S) {//運(yùn)算符棧出棧
    if (S.top == S.base) return ERROR;
    S.top--;
    return OK;

}

char GetTop1(SqStack1 S) {//運(yùn)算符棧取棧頂元素

    if (S.top != S.base)
        return *(S.top - 1);
}

typedef struct {//操作數(shù)棧
    double *base;
    double *top;
    int stacksize;
} SqStack2;

Status InitStack2(SqStack2 &S) {//操作數(shù)棧初始化
    S.base = new double[MAXSIZE];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

Status Push2(SqStack2 &S, double e) {//操作數(shù)棧入棧
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top = e;
    S.top++;
    return OK;
}

Status Pop2(SqStack2 &S) {//操作數(shù)棧出棧
    if (S.top == S.base) return ERROR;
    S.top--;
    return OK;
}

double GetTop2(SqStack2 S) {//操作數(shù)棧取棧頂元素
    if (S.top != S.base)
        return *(S.top - 1);
}

double Calculate(double a, char op, double b) {//計(jì)算表達(dá)式“a op b”的值
    switch (op) {
        case '+':
            return a + b;
            break;
        case '-':
            return a - b;
            break;
        case '*':
            return a * b;
            break;
        case '/':
            return a / b;
            break;
        default:
            return 0;
    }
}

char Precede(char a, char b) {//比較運(yùn)算符a和b的優(yōu)先級(jí) 沒什么好說的枚舉就完事了
    if ((a == '(' && b == ')') || (a == '=' && b == '='))return '=';
    else if (((a == '+' || a == '-' || a == '*' || a == '/' || a == ')') &&
              (b == '+' || b == '-' || b == ')' || b == '=')) ||
             ((a == '*' || a == '/' || a == ')') && (b == '*' || b == '/')))
        return '>';
    else if (((a == '(' || a == '=') && b != ')' && b != '=') || ((a == '+' || a == '-') && (b == '*' || b == '/')) ||
             a == '(' || b == '(')
        return '<';
}

bool judge(const char c) {
    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '=' || c == '(' || c == ')') return true;
    return false;
}

double EvaluateExpression(SqStack1 OPTR, SqStack2 OPND, char s[]) {//算術(shù)表達(dá)式求值的算符優(yōu)先算法
    //設(shè)OPTR和OPND分別為運(yùn)算符棧和操作數(shù)棧
    //表達(dá)式求值算法調(diào)用Precede函數(shù)和Calculate函數(shù)
    OPTR.top = OPTR.base;
    OPND.top = OPND.base;
    Push1(OPTR, '=');
    char theta;
    double a = 0, b = 0;
    int i = 0;
    while (s[i] != '=' || GetTop1(OPTR) != '=' && i < MAXSIZE) {
        // 對(duì)數(shù)字進(jìn)行解析
        if (!judge(s[i])) { // 解析數(shù)字求出數(shù)字
            // 整數(shù)部分
            double result = 0;
            while (s[i] != '.' && s[i] >= '0' && s[i] <= '9') {
                result = result * 10 + (s[i] - 48);
                ++i;
            }

            // 小數(shù)部分
            double result1 = 0;
            double Multiplier = 1.0 / 10;
            if (s[i] == '.') i++;

            while (s[i] >= '0' && s[i] <= '9') {
                result1 += Multiplier * (s[i] - 48);
                Multiplier *= 1.0 / 10;
                i++;
            }

            result += result1;
//            cout << result << endl;
            Push2(OPND, result);
        } else
            switch (Precede(GetTop1(OPTR), s[i])) {
                case '<':
                    Push1(OPTR, s[i]);
                    i++;
                    break;
                case '>':
                    theta = GetTop1(OPTR);
                    Pop1(OPTR);

                    a = GetTop2(OPND);
                    Pop2(OPND);
                    b = GetTop2(OPND);
                    Pop2(OPND);

                    Push2(OPND, Calculate(b, theta, a));
                    break;

                case '=':
                    Pop1(OPTR);
                    i++;
                    break;

            }
    }

    return GetTop2(OPND);
}

第2關(guān): 中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式

#include<iostream>

using namespace std;
#define  MAXSIZE  100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct {
    char *base;
    char *top;
    int stacksize;
} SqStack;

Status InitStack(SqStack &S) {//初始化棧
    S.base = new char[MAXSIZE];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

Status Push(SqStack &S, char e) {//入棧
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top = e;
    S.top++;
    return OK;
}

Status Pop(SqStack &S) {//出棧
    if (S.top == S.base) return ERROR;
    S.top--;
    return OK;
}

char GetTop(SqStack S) {//取棧頂元素
    if (S.top != S.base)
        return *(S.top - 1);
}

char Precede(char a, char b) {//比較運(yùn)算符a和b的優(yōu)先級(jí)
    if ((a == '(' && b == ')') || (a == '=' && b == '='))return '=';
    else if (((a == '+' || a == '-' || a == '*' || a == '/' || a == ')') &&
              (b == '+' || b == '-' || b == ')' || b == '=')) ||
             ((a == '*' || a == '/' || a == ')') && (b == '*' || b == '/')))
        return '>';
    else if (((a == '(' || a == '=') && b != ')' && b != '=') || ((a == '+' || a == '-') && (b == '*' || b == '/')) ||
             a == '(' || b == '(')
        return '<';
}

bool judge(const char c) {
    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '=' || c == '(' || c == ')') return true;
    return false;
}

void InfixToSuffix(SqStack OPTR, char s[]) {//將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式并輸出
    int i = 0;
    while ((s[i] != '=' || GetTop(OPTR) != '=') && s[i] != '\0') {
    if(!judge(s[i])){
        cout << s[i];
        i++;
    }
    else{
        switch (Precede(GetTop(OPTR),s[i])) {
            case '<':
                Push(OPTR,s[i]);
                i++;
                break;
            case '>':
                if(GetTop(OPTR) != ')' && GetTop(OPTR) != '(')
                cout << GetTop(OPTR);
                Pop(OPTR);
                break;

            case '=':
                if(GetTop(OPTR) != ')' && GetTop(OPTR) != '(')
                cout << GetTop(OPTR);
                Pop(OPTR);
                i++;
                break;
        }
    }
    }
    cout << endl;
}

第3關(guān)：基于棧的后綴算術(shù)表達(dá)式求值

#include <iostream>
#include<iomanip>
#include <string>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct {//操作數(shù)棧
    double *base;
    double *top;
    int stacksize;
} SqStack;

Status InitStack(SqStack &S) {//操作數(shù)棧初始化
    S.base = new double[MAXSIZE];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

Status Push(SqStack &S, double e) {//操作數(shù)棧入棧
    if (S.top - S.base == MAXSIZE) return ERROR;
    *S.top = e;
    S.top ++;
    return OK;
}

Status Pop(SqStack &S) {//操作數(shù)棧出棧
    if (S.top == S.base) return ERROR;
    S.top--;
    return OK;
}

double GetTop(SqStack S) {//操作數(shù)棧取棧頂元素
    if (S.top != S.base) return *(S.top - 1);
}

double Calculate(double a, char op, double b) {//計(jì)算表達(dá)式“a op b”的值
    switch (op) {
        case '+':
            return a + b;
            break;
        case '-':
            return a - b;
            break;
        case '*':
            return a * b;
            break;
        case '/':
            return a / b;
        default:
            return 0;
    }
}
bool judge(char c){
    if(c == '+' || c == '-' || c == '*' || c == '/' || c == '='  )
        return true;
    return false;
}
double EvaluateExpression(SqStack OPND, char s[]) {//后綴算術(shù)表達(dá)式求值
    //設(shè)OPND為操作數(shù)棧
    //表達(dá)式求值算法調(diào)用Calculate函數(shù)
    char theta;
    double a, b;
    int i = 0;
    while (s[i] != '='){
        if(s[i] == ' ') {
            i++;
            continue;
        }
        if(!judge(s[i])){
            double num = s[i] - 48;
            Push(OPND,num);
            i++;
            continue;
        }
        else{

            b = GetTop(OPND);
            Pop(OPND);
            a = GetTop(OPND);
            Pop(OPND);
            Push(OPND, Calculate(a,s[i],b));
            i++;
        }
        }
    return GetTop(OPND);
}

第4關(guān)：入棧和出棧的基本操作

#include<iostream>

using namespace std;
#define  MAXSIZE  100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct {
    int *base;
    int *top;
    int stacksize;
} SqStack;

Status InitSqStack(SqStack &S) {//棧的初始化
    S.base = new int [MAXSIZE];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

Status Push(SqStack &S, int e) {//入棧
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top = e;
    S.top++;
    return OK;
}

Status Pop(SqStack &S) {//出棧
    if (S.top == S.base) return ERROR;
    S.top--;
    return OK;
}

Status GetTop(SqStack S) {//取棧頂元素
    if (S.top != S.base)
        return *(S.top - 1);
    else return 0;
}
//本關(guān)任務(wù)：輸入一個(gè)整數(shù)序列a1,a2,a3...,an。當(dāng)ai不等于-1時(shí)將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂元素并將其出棧。
void InOutS(SqStack &S, int a[], int n) {//入棧和出棧的基本操作
    for (int i = 0; i < n; ++i) {
        if(a[i] != -1){
            Push(S,a[i]);
        }
        else{
            if(GetTop(S)){
                cout << GetTop(S) << endl;
                Pop(S);
            }
            else {
                cout << "POP ERROR" << endl;
                break;
        }
    }
}
}

第5關(guān)：雙棧的基本操作

基于棧的中綴算術(shù)表達(dá)式求值,算法,數(shù)據(jù)結(jié)構(gòu),c++ 文章來源地址http://www.zghlxwxcb.cn/news/detail-736356.html

#include<iostream>

using namespace std;
typedef int Status;
typedef struct {
    int top[2], bot[2];//棧頂和棧底指針
    int *V;//棧數(shù)組
    int m;//棧最大可容納元素個(gè)數(shù)
} DblStack;

void InitDblStack(DblStack &S, int m) {//初始化一個(gè)大小為m的雙向棧
    S.V = new int[m];
    if(!S.V) return;
    S.bot[0] = S.top[0] = -1;
    S.bot[1] = S.top[1] = m;
    return;
}

Status IsEmpty(DblStack S, int i) {//判斷指定的i號(hào)棧是否為空，空返回1，否則返回0
    if (S.top[i] == S.bot[i]) return 1;
    return 0;
}

Status IsFull(DblStack S) {//判斷棧是否滿，滿則返回1，否則返回0
    if (S.top[0] + 1 == S.top[1])
        return 1;
    return 0;
}

void Push(DblStack &S, int i) {//向指定的i號(hào)棧中插入元素x，先移動(dòng)指針再入棧
    int x;
    cin >> x;
    if (IsFull(S)) return;
    if (i == 0) {
        S.V[++S.top[0]] = x;
    } else {
        S.V[--S.top[1]] = x;
    }

}

void Pop(DblStack &S, int i) {//刪除指定的i號(hào)棧的棧頂元素，先出棧再移動(dòng)指針
    if (S.top[i] == S.bot[i]) {
        return;
    }

    if (i == 0) {
        cout << S.V[S.top[0]--] << ' ';
    } else if (i == 1) {
        cout << S.V[S.top[1]++] << ' ';
    }
    return;
}

第6關(guān): 基于棧的回文字符序列判斷

#include <iostream>

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct {
    char *base;
    char *top;
    int stacksize;
} SqStack;

Status InitStack(SqStack &S) {//棧初始化
    S.base = new char[MAXSIZE];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

Status Push(SqStack &S, char e) {//入棧
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top = e;
    S.top++;
    return OK;
}

Status Pop(SqStack &S) {//出棧返回棧頂元素
    if(S.top == S.base) return ERROR;
    S.top--;
}
char  Get(SqStack &S){
    if(S.top == S.base) return 0;
    return *(S.top - 1);
}
Status IsPalindrome(SqStack &S, char *t) {//判斷棧的回文字符序列，不等則返回零, 相等則返回1
    int i = 0;
    while (t[i] != '\0'){
//        cout << t[i] << endl;
        Push(S,t[i]);
        i++;
    }
    i--;
    for (int j = 0; j < i; ++j) {
        char e = Get(S);
        if(t[j] != e) return 0;
        Pop(S);
    }
    return 1;

}

第7關(guān)：基于棧的可操作判斷

#include <iostream>

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct {
    char *base;
    char *top;
    int stacksize;
} SqStack;

Status InitStack(SqStack &S) {//初始化棧
    S.base = new char[MAXSIZE];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

Status Push(SqStack &S) {//入棧
    if (S.top - S.base == S.stacksize) return ERROR;
    S.top++;
    return OK;
}

Status Pop(SqStack &S) {//出棧
    S.top--;
}

Status IsEmpty(SqStack S) {//判斷棧是否為空，空返回1，否則返回0
    if(S.top == S.base) return 1;
    return 0;
}

bool Judge(char a[], SqStack &S) {//棧的可操作判斷
int pos = 0;
    while (a[pos] != '\0'){
        if(a[pos] == 'I') Push(S);
        else {
            if(IsEmpty(S)) return 0;
            else Pop(S);
        }
        pos++;
    }
    return IsEmpty(S);
}

第8關(guān)：Ackermann函數(shù)的遞歸求值

#include<iostream>

using namespace std;

int Ack(int m, int n) {//Ackermann函數(shù)的遞歸求值
    if (m == 0) return n + 1;
    if (m > 0 && n == 0) return Ack(m - 1, 1);
    return Ack(m - 1, Ack(m, n - 1));
}

第9關(guān)：Ackermann函數(shù)的非遞歸求值

#include<iostream>

using namespace std;
#define MAXSIZE 100

int Ack(int m, int n) {//Ackermann函數(shù)的非遞歸求值
    int arrary[m + 1][MAXSIZE ];
    for (int j = 0; j < MAXSIZE; j++)
        arrary[0][j] = j + 1;
    for (int i = 1; i <= m; i++) {
        arrary[i][0] = arrary[i - 1][1];
        for (int j = 1; j < MAXSIZE; j++)
            arrary[i][j] = arrary[i - 1][arrary[i][j - 1]];
    }
    return (arrary[m][n]);
}

第10關(guān)：遞歸求解單鏈表中的最大值

#include <iostream>
#include "algorithm"
using namespace std;
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

void CreateList_R(LinkList &L, int n) {//后插法創(chuàng)建單鏈表
   L = new LNode();
   LinkList pre = L;
    for (int i = 0; i < n; ++i) {
        LinkList cur = new LNode();
        cin >> cur->data;
        pre->next = cur;
        pre = pre->next;
    }
}

int GetMax(LinkList L) {//遞歸求解單鏈表中的最大值
    if( L == nullptr) return INT32_MIN;
    return max(L->data, GetMax(L->next));
}

第11關(guān)：遞歸求解單鏈表中的結(jié)點(diǎn)個(gè)數(shù)

#include <iostream>

using namespace std;
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

void CreateList_R(LinkList &L, int n) {//后插法創(chuàng)建單鏈表
    L = new LNode();
    LinkList pre = L;
    for (int i = 0; i < n; ++i) {
        LinkList cur = new LNode();
        cin >> cur->data;
        pre->next = cur;
        pre = pre->next;
    }
}

int GetLength(LinkList L) {//遞歸求解單鏈表中的結(jié)點(diǎn)個(gè)數(shù)
    if(L == nullptr)return 0;
    return 1 + GetLength(L->next);
}

第12關(guān)：遞歸求解單鏈表中的平均值

#include <iostream>

using namespace std;
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

void CreateList_R(LinkList &L, int n) {//后插法創(chuàng)建單鏈表
    L = new LNode();
    LinkList pre = L;
    for (int i = 0; i < n; ++i) {
        LinkList cur = new LNode();
        cin >> cur->data;
        pre->next = cur;
        pre = pre->next;
    }
}

double GetAverage(LinkList L, int n) {//遞歸求解單鏈表中的平均值
    if (L == nullptr) return 0;
    if(n == 1) return L->data;
    return (L->data + (n - 1) * GetAverage(L->next, n - 1)) / n;
}

第13關(guān)：基于循環(huán)鏈表的隊(duì)列的基本操作

#include<iostream>

using namespace std;
typedef int Status;
typedef struct QNode {//隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
    int data;
    struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
    QueuePtr rear;    //只設(shè)一個(gè)隊(duì)尾指針
} LinkQueue;

Status EmptyQueue(LinkQueue Q) {//判斷隊(duì)列是否為空，空返回1，否則返回0
//隊(duì)列只有一個(gè)頭結(jié)點(diǎn)，即當(dāng)頭結(jié)點(diǎn)的指針域指向自己時(shí)，隊(duì)列為空
    if (Q.rear->next == Q.rear) return 1;
    return 0;
}

void EnQueue(LinkQueue &Q, int e) {//入隊(duì)，插入元素e為Q的新的隊(duì)尾元素
    QueuePtr queuePtr = new QNode();
    queuePtr->data = e;
    queuePtr->next = Q.rear->next;
    Q.rear->next = queuePtr;
    Q.rear = Q.rear->next;
}

void DeQueue(LinkQueue &Q) {//出隊(duì)，輸出Q的隊(duì)頭元素值，后將其刪除
    QueuePtr q = Q.rear->next->next;
    cout << q->data << ' ';
    Q.rear->next->next = q->next;
    if (q == Q.rear) {
        Q.rear = Q.rear->next;
    }

}

第14關(guān)：附加判定標(biāo)志的循環(huán)隊(duì)列的基本操作

#include<iostream>

using namespace std;
#define MAXSIZE 100
#define OK 0
#define OVERFLOW -1
#define ERROR -2
typedef int Status;
typedef struct {
    int *base;
    int front, rear, tag;
} SqQueue;

Status InitQueue(SqQueue &Q) {//構(gòu)造一個(gè)空隊(duì)列Q
    Q.base = new int[MAXSIZE];
    if (!Q.base) return ERROR;
    Q.front = Q.rear = 0;
    return OK;
}

Status EnQueue(SqQueue &Q, int e) {//插入元素e為Q的新的隊(duì)尾元素
    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

Status DeQueue(SqQueue &Q) {//刪除Q的隊(duì)頭元素，用e返回其值
    if (Q.front == Q.rear) return ERROR;
    auto e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return e;
}

第15關(guān)：基于兩端操作的循環(huán)隊(duì)列的實(shí)現(xiàn)

#include<iostream>

using namespace std;
#define MAXSIZE 100
#define OK 0
#define OVERFLOW -1
#define ERROR -2
typedef int Status;
typedef struct {
    int *base;
    int front, rear, tag;
} SqQueue;

Status InitQueue(SqQueue &Q) {//構(gòu)造一個(gè)空隊(duì)列Q
    Q.base = new int[MAXSIZE];
    if (!Q.base) return ERROR;
    Q.front = Q.rear = 0;
    return OK;
}

Status EnQueue(SqQueue &Q, int e) {//插入元素e為Q的新的隊(duì)尾元素
    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

Status DeQueue(SqQueue &Q) {//刪除Q的隊(duì)頭元素，用e返回其值
    if (Q.front == Q.rear) return ERROR;
    auto e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return e;
}

到了這里，關(guān)于北京林業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二基于棧的算術(shù)表達(dá)式求值算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！