棧練習——逆波蘭表達式

逆波蘭表達式

• 可參照文章

算法分析

• 若目前字元是操作數，則壓棧
• 若目前字元是操作符，則彈出棧中的兩個操作數，計算後仍然壓入棧中

C++代碼實作

/*
字尾表達式（逆波蘭表達式）
有效操作隻有'+'、'-'、'*'、'/'，且操作數是整數
*/
#include<iostream>
#include<string>
#include<assert.h>
#include<cstring>

using namespace std;

#define OVERFLOW -2
#define OK 1
#define ERROR -1

typedef int Status;
typedef int SElemType;

typedef struct StackNode {
    SElemType data;
    struct StackNode* next;
}StackNode, * LinkStack;

// 鍊棧初始化
void InitStack(LinkStack& S) {
    S = NULL;
}

// 判斷鍊棧是否為空
Status StackEmpty(LinkStack S) {
    if (S == NULL) return 1;
    else return 0;
}

// 得到棧頂元素
Status GetTop(LinkStack S, SElemType& e) {
    if (StackEmpty(S)) return ERROR;
    e = S->data;
    return OK;
}

// 判斷棧中是否隻有一個元素
bool IsOne(LinkStack S) {
    if (StackEmpty(S)) return false;
    LinkStack p;
    p = S;
    int i = 0;
    while (p) {
        i++;
        p = p->next;
    }
    if (i == 1) return true;
    else return false;
}

// 入棧
Status Push(LinkStack& S, SElemType e) {
    LinkStack p;
    p = new StackNode;
    if (!p) exit(OVERFLOW);
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}

// 出棧
Status Pop(LinkStack& S, SElemType& e) {
    if (StackEmpty(S)) return ERROR;
    LinkStack p;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    p = NULL;
    return OK;
}

// 判斷是否為數字
bool IsNum(char ch) {
    if (ch > '0' && ch < '9')
        return true;
    return false;
}

Status f(const char* str, SElemType& e) {
//    const char* str = str.c_str();
    assert(str);  // 斷言 參數
    int size = strlen(str);
    int i = 0;
    LinkStack S;
    InitStack(S);
    int temp = 0;
    for (; i < size; i++) {
        if (IsNum(str[i]))
            // 轉換為數字
            temp = temp * 10 + str[i] - '0'; 
        else if (str[i] == ' ') {
            if (IsNum(str[i - 1])) {
                // 目前字元為空格，且前一個為數字，入棧
                Push(S, temp);
                temp = 0;
            }
        }
        else {
            if (IsOne(S)) {
                // 棧中隻有一個元素
                cout << "表達式有誤，無法計算！" << endl;
                return ERROR;
            }
            Pop(S, e);
            int a = e;  // 右操作數
            Pop(S, e);
            int b = e;  // 左操作數
            switch (str[i]) {
            case '+':
                Push(S, b + a);
                break;
            case '-':
                Push(S, b - a);
                break;
            case '*':
                Push(S, b * a);
                break;
            case '/':
                if (a == 0) {
                    cout << "被除數為零，無法計算！" << endl;
                    return ERROR;
                }
                else {
                    Push(S, b / a);
                    break;
                }
            }
        }

    }
    if (!IsOne(S)) {
        cout << "表達式操作數過多！" << endl;
        return ERROR;
    }
    else {
        Pop(S, e);
        e = e;
        return OK;
    }

}

int main()
{
    SElemType e;
    const char* str = "1 3 + 4 * 4 /";
    f(str, e);
    cout << "結果為: " << e;
    return 0;
}           

結果為: 4