栈基础：后缀表达式求值

后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

如：$\texttt{3*(5-2)+7}$ 对应的后缀表达式为：$\texttt{3.5.2.-*7.+@}$。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 $s$，表示后缀表达式。

输出格式

输出一个整数，表示表达式的值。

样例 #1

样例输入 #1

3.5.2.-*7.+@

样例输出 #1

16

提示

数据保证，$1 \leq |s| \leq 50$，答案和计算过程中的每一个值的绝对值不超过 $10^9$。

以下为c++用stl写的代码

int main()
{
    cin>>c;
    int a=0,b=0;
    int i,j;
    for(int k=0;k<c.length();k++)
    {
        if(c[k]=='@') break;
        else if(c[k]=='.'){
            q.push(a);
            b=0,a=0;
        }
        else if(c[k]<='9'&&c[k]>='0'){
            a=b*10+c[k]-'0';
            b=a;
        }
        else{

            if(c[k]=='-') i=q.top(),q.pop(),j=q.top(),q.pop(), q.push(j-i);
            if(c[k]=='+') i=q.top(),q.pop(),j=q.top(),q.pop(), q.push(j+i);
            if(c[k]=='*') i=q.top(),q.pop(),j=q.top(),q.pop(), q.push(j*i);
            if(c[k]=='/') i=q.top(),q.pop(),j=q.top(),q.pop(), q.push(j/i);
        }
    }
    cout<<q.top()<<endl;

}

以下为c语言（掺了一点c++的水，关键部分还是用c语言和cpp共有的函数写的）原始人代码

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#define maxsize 100
using namespace std;

typedef struct sttack{
    int st[maxsize];
    int top;
}stack;
stack *init_stack(){
    stack *st;
    st = (stack*)malloc(sizeof(stack));
    st->top =-1; 
    return st;
}
int push(stack *s,int x){
    if(s->top+1>=maxsize )
    {
        return 0;
    }
    else
    {
        s->top++;
        s->st[s->top]=x;
    }
    return 1;
}
int pop(stack *s){
    long long ret;
    if(s->top<=-1){
        return 0;
    }
    else{
        ret=s->st [s->top ];
        s->top--;
    }
    return ret;
}
void printstack(stack *s){
    while((*s).top !=-1){
        printf("%d",(*s).st [s->top]);
        s->top--; 
    }
}

int main(void){

    stack *st;
    st = init_stack();
    char ch[15],c;
    int i=0;
    long long tar,a1,a2;
    cin>>c;
    while(c!='@')
    {
        if(c>='0' && c<='9')
        {
            while(c!='.')
              {
                ch[i]=c;
                i++;
                cin>>c;
            }
            i=0;
            tar=atol(ch);
            push(st,tar);
            memset(ch,0,sizeof(ch));//memset函数用于清空字符串ch的值
        }
        else if(c=='+')
        {
            a1=pop(st);
            a2=pop(st);
            push(st,a1+a2);
        }
        else if(c=='-')
        {
            a1=pop(st);
            a2=pop(st);
            push(st,a2-a1);
        }
        else if(c=='*')
        {
            a1=pop(st);
            a2=pop(st);
            push(st,a1*a2);
        }
        else if(c=='/')
        {
            a1=pop(st);
            a2=pop(st);
            push(st,a2/a1);
        }
        cin>>c;
    }
    cout<<st->st [st->top ]<<endl;


    free(st);return 0;
}