给定牛牛一个后缀表达式s,计算它的结果,例如,1+1对应的后缀表达式为1#1#+,‘#’作为操作数的结束符号。
其中,表达式中只含有‘+’、’-‘、’*‘三种运算,不包含除法。
本题保证表达式一定合法,且计算过程和计算结果的绝对值一定不会超过
"1#1#+"
2
1#1#+这个后缀表达式表示的式子是1+1,结果为2
"12#3#+15#*"
225
12#3#+15#*这个后缀表达式表示的式子是(12+3)*15,结果为225
#include <errno.h> // #define OK 1 // #define ERROR -1 // #define MEMORY_OVERFLOW -2 typedef enum { OK = 1, ERROR = -1, MEMORY_OVERFLOW = -2 } Status; #define NOT ! #define DEFAULT_CAPACITY 8 #define InitStack(S) __InitStack(S, DEFAULT_CAPACITY) typedef long long LL; // ==================== 顺序栈存储结构表示与实现 ==================== typedef LL SElemType; typedef struct { SElemType* base; SElemType* top; size_t capacity; } SqStack; Status __InitStack(SqStack* S, int initialCapacity) { if (initialCapacity < 1) { fprintf(stderr, "__InitStack ERROR: The initialCapacity %d Must be > 0!", initialCapacity); return ERROR; } if (!((*S).base = (SElemType*) malloc(initialCapacity * sizeof(SElemType)))) { fprintf(stderr, "__InitStack Memory Overflow: %s\n", strerror(errno)); exit(MEMORY_OVERFLOW); } (*S).top = (*S).base; (*S).capacity = initialCapacity; return OK; } int StackEmpty(SqStack* S) { return (*S).top == (*S).base; } int StackFull(SqStack* S) { return (*S).top - (*S).base == (*S).capacity; } size_t StackLength(SqStack* S) { return (*S).top - (*S).base; } void __large_capacity(SqStack* S) { if (!((*S).base = (SElemType*) realloc((*S).base, ((*S).capacity << 1) * sizeof(SElemType)))) { fprintf(stderr, "__large_capacity Memory Overflow: %s\n", strerror(errno)); exit(MEMORY_OVERFLOW); } (*S).top = (*S).base + (*S).capacity; (*S).capacity <<= 1; } Status Push(SqStack* S, SElemType e) { if (StackFull(S)) __large_capacity(S); *(*S).top++ = e; return OK; } Status Pop(SqStack* S, SElemType* e) { if (StackEmpty(S)) { fputs("Pop ERROR: The stack is empty!\n", stderr); return ERROR; } *e = *--(*S).top; return OK; } Status DestroyStack(SqStack* S) { free((*S).base); (*S).top = NULL; return OK; } // ==================== 顺序栈存储结构表示与实现 ==================== /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定一个后缀表达式,返回它的结果 * @param str string字符串 * @return long长整型 */ long long legalExp(char* str) { SqStack S; InitStack(&S); LL num = 0, n1, n2; while (*str) { switch (*str) { case '+': Pop(&S, &n2); Pop(&S, &n1); Push(&S, n1 + n2); break; case '-': Pop(&S, &n2); Pop(&S, &n1); Push(&S, n1 - n2); break; case '*': Pop(&S, &n2); Pop(&S, &n1); Push(&S, n1 * n2); break; case '#': Push(&S, num); num = 0; break; default: // numerical num = num * 10 + *str - 48; break; } ++str; } LL ans; Pop(&S, &ans); DestroyStack(&S); return ans; }
long long legalExp(string str) { stack<long long> operand; long long a=0; for(int i=0;i<str.length();i++) { if(str[i]>='0'&&str[i]<='9') a=a*10+str[i]-'0'; switch(str[i]) { case '#' : if(str[i+1]>='0'&&str[i+1]<='9') { operand.push(a); a=0; } break; case '+': a=operand.top()+a; break; case '-': a=operand.top()-a; break; case '*': a=operand.top()*a; break; default: break; } if(str[i]=='+'||str[i]=='-'||str[i]=='*') { operand.pop(); if(i+1<str.length()&&str[i+1]>='0'&&str[i+1]<='9') { operand.push(a); a=0; } } } return a; }