波兰表达式输出原运算式结果

舍友的数据结构作业，顺道学习

样例输入：一个波兰表达式，每个元素空格分隔，结束符为#。

orz（手模栈真ex！D区）好是我太菜了

注释写的比较多了

没毛病 就是一个纯粹的令人讨厌的模拟  stack不香? 

总结&&发现：stack是真好使

从一篇大佬的博客上学到的新函数：atof()   char数组转double型   好方便%%% 不过下面没有用

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define MAXSIZE 100///栈最大容量
using namespace std;
typedef struct
{
    string *base;///栈底指针 string类型
    string *top;///栈顶指针
    int siz;///当前栈大小
    int maxx;
} SqStack;

void Init(SqStack &S)///初始化
{
    S.base=(string *)malloc(MAXSIZE*sizeof(string));
    S.top=S.base;
    S.maxx=MAXSIZE;
    S.siz=0;///现在这个栈是空的
}

string GetTop(SqStack S)
{
    string e;
    e=*(S.top-1);
    return e;
}

void Push(SqStack &S,string e)
{
    *S.top=e;
    S.top++;
    S.siz++;
}

string Pop(SqStack &S)
{
    string e;
    e=*(S.top-1);
    S.top--;
    S.siz--;
    return e;
}

string ntos(int a)
{
    string s;
    while(a)
    {
        int k=a%10;
        char c=k+'0';
        s=c+s;
        a/=10;
    }
    return s;
}

int ston(string s)
{
    int ans=0;
    int len=s.size();
    for(int i=0;i<len;i++)
    {
        ans=ans*10+s[i]-'0';
    }
    return ans;
}

int Operate(int tmp1,string c,int tmp2)
{
    int ans=0;
    switch(c[0])
    {
        case '+':ans=tmp1+tmp2;break;
        case '-':ans=tmp1-tmp2;break;
        case '*':ans=tmp1*tmp2;break;
        case '/':ans=tmp1/tmp2;break;
    }
    return ans;
}

int main()
{
    SqStack S;
    Init(S);
    string a,b,c;
    cout<<"请输入波兰表达式"<<endl;
    while(cin>>a)
    {
        if(a=="#")
            break;
        int len=a.size();
        if(a[0]>='0'&&a[0]<='9'&&S.siz>=2)///该字符串是数字串&&栈内至少还有俩元素（一个数字串一个运算符），如果少于两个元素肯定不能进行运算，直接把它压入栈（else）
        {
            int tmp1=ston(a);
            while(S.siz>=2)///比如- 2 * 3 1,算完了3*1后再算2-3,直到栈顶不是一个运算符和俩数字串相邻或栈内元素少于2个
            {
                b=Pop(S);///弹出一个元素
                if(b[0]>='0'&&b[0]<='9')
                {
                    int tmp2=ston(b);
                    string c=Pop(S);
                    tmp1=Operate(tmp2,c,tmp1);///如果b是个数字串的话,c一定是个运算符！否则该表达式没法算，不合法。所以不需要判断c是个什么东西，直接运算。注意运算顺序，后出栈的在前。
                    if(S.siz<2)///现在栈里少于两个元素，不需要在循环了
                    {
                        a=ntos(tmp1);///把刚才算出来的结果转化成字符串
                        Push(S,a);///压入栈
                        break;///这个循环告一段落，去处理新来的字符串
                    }
                }
                else///刚弹出的元素是个运算符，算不了
                {
                    Push(S,b);///再把它放回去
                    Push(S,a);///刚才新来的字符串也需要放进去
                    break;///不能再算了，算不了，去处理新接收的字符串叭
                }
            }
        }
        else
            Push(S,a);
    }
    ///输入结束的同时，栈顶只会留有一个元素，就是结果
    int ans=ston(GetTop(S));///记得转int嗷~
    cout<<"表达式的值为"<<ans<<'\n';
    return 0;
}
///- + 4 * 2 3 / 10 5 #
///- + 2 3 * 4 - 5 1 #