简单的逆波兰式求表达式值算法

Reverse Polish notation calculate

#include <iostream>
using namespace std;

/**
 * @brief 栈结构体
 * 
 */
typedef struct Stack
{
    int data;
    Stack *next;
} Stack;

/**
 * @brief 链表结构体
 * 
 */
typedef struct List
{
    int data;
    char type;
    List *next;
} * RPN, ListNode;

/**
 * @brief 判断是否空栈
 * 
 * @param s 栈顶指针
 * @return true 空栈
 * @return false 非空栈
 */
bool Empty(Stack *s)
{
    if (s->next == NULL)
        return true;
    else
        return false;
}

/**
 * @brief 判断是否空表
 * 
 * @param l 链表头指针
 * @return true 空表
 * @return false 非空表
 */
bool Empty(List *l)
{
    if (l->next == NULL)
        return true;
    else
        return false;
}

/**
 * @brief 尾插法添加链表节点
 * 
 * @param l 链表头指针
 * @param data 链表数据
 * @param type 链表数据类型
 */
void AppendList(List *l, int data, char type)
{
    ListNode *i = l;
    while (i->next != NULL)
    {
        i = i->next;
    }

    ListNode *n = new ListNode();
    n->data = data;
    n->type = type;
    n->next = NULL;

    i->next = n;
}

/**
 * @brief 入栈
 * 
 * @param stack 栈顶指针
 * @param data 入栈数据
 */
void Push(Stack *stack, int data)
{
    Stack *t = new Stack();
    t->data = data;
    t->next = stack->next;
    stack->next = t;
}

/**
 * @brief 出栈
 * 
 * @param stack 栈顶指针
 * @param data 出栈数据
 */
void Pop(Stack *stack, int &data)
{
    if (Empty(stack))
        return;
    Stack *t = stack->next;
    data = t->data;
    stack->next = t->next;
    free(t);
}

/**
 * @brief 计算操作
 * 
 * @param left 左操作数
 * @param ope 操作符
 * @param right 右操作数
 * @return int 计算结果
 */
int calc(int left, char ope, int right)
{
    switch (ope)
    {
    case '+':
        return (left + right);
        break;
    case '-':
        return (left - right);
        break;
    case '*':
        return (left * right);
        break;
    case '/':
        return (left / right);
        break;
    default:
        return 65535;
    }
}

/**
 * @brief 计算逆波兰式结构
 * 
 * @param rpn 逆波兰式链表头指针
 * @return int 计算结果
 */
int calc(RPN rpn) {
    Stack *num = new Stack();
    for (RPN i = rpn->next; i != NULL; i = i->next)
    {
        if (i->type == 'c')
        {
            int left, right, ope = i->data;
            Pop(num, right);
            Pop(num, left);
            Push(num, calc(left, ope, right));
        }
        else
        {
            Push(num, i->data);
        }
    }
    free(num);
    return num->next->data;
}

/**
 * @brief 操作优先级
 * 
 * @param ope 操作符
 * @return int 优先级
 */
int priority(char ope)
{
    switch (ope)
    {
    case '+':
        return 1;
        break;
    case '-':
        return 1;
        break;
    case '*':
        return 2;
        break;
    case '/':
        return 2;
        break;
    case '(':
        return 3;
        break;
    case ')':
        return 0;
        break;
    default:
        return 0;
    }
}

/**
 * @brief 生成逆波兰式链表
 * 
 * @param exp 原始表达式
 * @return RPN 逆波兰式链表头指针
 */
RPN RPNinit(string exp)
{
    RPN rpn = new List();
    Stack *ope = new Stack();
    int flag = 0;
    for (int i = 0; i <= exp.length(); i++)
    {
        if (i < exp.length() && exp[i] >= '0' && exp[i] <= '9')
        {
            flag = (flag == -1 ? 0 : flag) * 10 + (exp[i] - '0');
        }
        else
        {
            if (flag != -1)
            {
                AppendList(rpn, flag, 'n');
            }

            while (!Empty(ope) && priority(ope->next->data) >= priority(char(exp[i])) && (ope->next->data != '(' || exp[i] == ')'))
            {
                int data;
                Pop(ope, data);
                if (data == '(')
                    break;
                AppendList(rpn, data, 'c');
            }
            if (exp[i] != ')')
                Push(ope, exp[i]);
            flag = -1;
        }
    }
    free(ope);
    return rpn;
}

int main()
{
    string expression;
    cin >> expression;

    RPN rpn = RPNinit(expression);

    cout << calc(rpn) << endl;
    return 0;
}