首页 > 试题广场 >

牛牛与后缀表达式

[编程题]牛牛与后缀表达式
  • 热度指数:299 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定牛牛一个后缀表达式s,计算它的结果,例如,1+1对应的后缀表达式为1#1#+,‘#’作为操作数的结束符号。
其中,表达式中只含有‘+’、’-‘、’*‘三种运算,不包含除法。
本题保证表达式一定合法,且计算过程和计算结果的绝对值一定不会超过
示例1

输入

"1#1#+"

输出

2

说明

1#1#+这个后缀表达式表示的式子是1+1,结果为2 
示例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;
}

发表于 2021-07-16 20:01:51 回复(0)
可能比较简洁的版本
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;
}


发表于 2021-02-07 14:32:27 回复(0)
这个也太简单了,是不是考验代码优不优美。用std::string,用find获取两个#位置,其他直接计算即可。
发表于 2021-01-22 18:50:32 回复(0)