逆波兰表达式

• 可参照文章逆波兰表达式

算法分析

• 若当前字符是操作数，则压栈
• 若当前字符是操作符，则弹出栈中的两个操作数，计算后仍然压入栈中

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