表达式计算

第一步

定义链栈

typedef struct Snode{
    int data;
    struct Snode *next;
}Snode , *LinkStack;

第二步

初始化栈

bool InitStack(LinkStack &s){
    s = NULL;
    return true;
}

第三步

判断是否为空

bool Empty(LinkStack s){
    if(s == NULL) return true;
    return false;
}

第四步

入栈

bool Push(LinkStack &s , int e){
    LinkStack p = new Snode;
    p -> data = e;
    p -> next = s;
    s = p;
    return true;
}

第五部

出栈

//出栈
bool Pop(LinkStack &s , int &e){
    if(Empty(s)) return false;
    e = s->data;
    LinkStack p = s;
    s = s->next;
    delete p;
    return true;
}

第六步

取栈顶元素

int GetTop(LinkStack s){
    if(Empty(s)) return false;
    return s->data;
}

第七步

抄完书了，开始写

int main()
{
    LinkStack s;        //定义链栈
    InitStack(s);        // 初始化链栈
    string a;            //定义字符串 a 这里是c++的用法，为什么我非要用c++呢，
// 当然是想让你们自己写啦，哈哈，这里等价于 char a[100];
    cin>>a;            // 输入字符串a
    reverse(a.begin(), a.end());   //c++内置函数，包含在#include<algorithm>头文件，反转字符串，知道大家没学过，哈哈，自己尝试写写这个函数吧
    int t = 0,t1 = 0;   // 定义两个临时变量，下边要用
    for(int i = 0 ;i < a.length() ;i++){        //a.length(),c++内置函数，大家自己写写，或者，你去网上熟练的搜下它怎么用。
        if(a[i] >= '0' && a[i] <= '9') Push(s,a[i]-'0'); 
//如果输入的前缀表达式，是数字的话，就把这个字符所对应的数字，放入栈里
//比如 0 = ‘0’-‘0’ 1 = ‘1’ - ‘0’ ；
        else {                    //如果是运算符，就从栈里拿出两个元素进行运算
            if(!Empty(s)) Pop(s, t);
            if(!Empty(s)) Pop(s, t1);
            int sum = 0;
            switch (a[i]) {
                case '+':
                    sum = t + t1;
                    break;
                case '-':
                    sum = t - t1;
                    break;
                case '*':
                    sum = t * t1;
                    break;
                case '/':
                    sum = t / t1;
                    break;
                default:
                    break;
            }
            Push(s, sum);        //把运算后的结果放进栈中
        }
    }
//最后当循环结束的时候，大家会发现，栈中只有一个元素，就是我们输入的前缀表达式的值
    cout << GetTop(s)<<"\n";   //输出结果，over
    return 0;
}

完整代码

//
//  main.cpp
//  数据结构3
//
//  Created by 宋玉良 on 2020/10/29.
//
#include<bits/stdc++.h>
using namespace std;
typedef struct Snode{
    int data;
    struct Snode *next;
}Snode , *LinkStack;
//初始化
bool InitStack(LinkStack &s){
    s = NULL;
    return true;
}
//判断是否为空
bool Empty(LinkStack s){
    if(s == NULL) return true;
    return false;
}
//入栈
bool Push(LinkStack &s , int e){
    LinkStack p = new Snode;
    p -> data = e;
    p -> next = s;
    s = p;
    return true;
}
//出栈
bool Pop(LinkStack &s , int &e){
    if(Empty(s)) return false;
    e = s->data;
    LinkStack p = s;
    s = s->next;
    delete p;
    return true;
}
//取栈顶元素
int GetTop(LinkStack s){
    if(Empty(s)) return false;
    return s->data;
}

int main()
{
    LinkStack s;
    InitStack(s);
    string a;
    cin>>a;
    reverse(a.begin(), a.end());
    int t = 0,t1 = 0;
    for(int i = 0 ;i < a.length() ;i++){
        if(a[i] >= '0' && a[i] <= '9') Push(s,a[i]-'0');
        else {
            if(!Empty(s)) Pop(s, t);
            if(!Empty(s)) Pop(s, t1);
            int sum = 0;
            switch (a[i]) {
                case '+':
                    sum = t + t1;
                    break;
                case '-':
                    sum = t - t1;
                    break;
                case '*':
                    sum = t * t1;
                    break;
                case '/':
                    sum = t / t1;
                    break;
                default:
                    break;
            }
            Push(s, sum);
        }
    }
    cout << GetTop(s)<<"\n";
    return 0;
}