链栈实现后缀表达式求值c++

好的，链栈实现后缀表达式求值的思路如下：

1. 定义一个链栈结构体，包含数据域和指向下一个节点的指针域。
2. 遍历后缀表达式，如果是数字则入栈，如果是运算符则弹出栈顶的两个数字进行运算，并将结果入栈。
3. 最后栈中剩下的数字即为表达式的结果。

以下是代码实现：

#include <iostream>
#include <string>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class LinkedStack {
public:
    LinkedStack() {
        top = nullptr;
    }

    ~LinkedStack() {
        while (top != nullptr) {
            Node* temp = top;
            top = top->next;
            delete temp;
        }
    }

    void push(int x) {
        Node* newNode = new Node;
        newNode->data = x;
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (top == nullptr) {
            return -1; // 栈为空
        }
        int x = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return x;
    }

    int peek() {
        if (top == nullptr) {
            return -1; // 栈为空
        }
        return top->data;
    }

    bool isEmpty() {
        return top == nullptr;
    }

private:
    Node* top;
};

int evaluatePostfix(string postfix) {
    LinkedStack stack;
    for (char c : postfix) {
        if (isdigit(c)) {
            stack.push(c - '0');
        } else {
            int operand2 = stack.pop();
            int operand1 = stack.pop();
            switch (c) {
                case '+':
                    stack.push(operand1 + operand2);
                    break;
                case '-':
                    stack.push(operand1 - operand2);
                    break;
                case '*':
                    stack.push(operand1 * operand2);
                    break;
                case '/':
                    stack.push(operand1 / operand2);
                    break;
            }
        }
    }
    return stack.pop();
}

int main() {
    string postfix = "23+4*";
    int result = evaluatePostfix(postfix);
    cout << "Result: " << result << endl;
    return 0;
}