计算逆波兰式（后缀表达式）的值

计算逆波兰式（后缀表达式）的值
运算符仅包含"+","-","*"和"/"，被操作数是整数

保证表达式合法，除法时向下取整。

数据范围：表达式的长度满足： n \le 10000n≤10000
进阶：空间复杂度 O(n)O(n) ， 时间复杂度 O(n)O(n)

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> numbers;
        for(auto token : tokens)
        {
            if(token == "+" || token == "-" || token == "*" || token == "/")
             {
                int a,b,res;
                b=numbers.top();numbers.pop();
                a=numbers.top();numbers.pop();
                if(token == "+")
                    res=a+b;
                else if(token == "-")
                    res=a-b;
                else if(token == "*")
                    res=a*b;
                else
                    res=a/b;
                 numbers.push(res);
             }
            else
            {
                stringstream ss;
                ss<<token;
                int temp;
                ss>>temp;
                numbers.push(temp);
            }
        }
        return numbers.top();
    }
};

参考

C语言 后缀表达式_Xunzi229的博客-CSDN博客_后缀表达式c语言 维基百科逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。中缀表达式 后缀表达式 1 + 2 1 2 + 1 + （2 - 3）/ 4 1 2... https://blog.csdn.net/Xunzi229/article/details/93379661?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~aggregatepage~first_rank_ecpm_v1~rank_aggregation-1-93379661.pc_agg_rank_aggregation&utm_term=c%E8%AF%AD%E8%A8%80%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E8%BF%90%E7%AE%97&spm=1000.2123.3001.4430

// 逆波兰表达式， 后缀表达式  运算发放在后面
 
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
 
typedef double DateType;
 
typedef struct RpnNode{
  DateType data;
  struct RpnNode *next;
}RpnNode, *RpnNodeList;
 
typedef struct RpnNodeSave{
  RpnNodeList top;
  int count;
}RpnNodeSave;
 
// 进站
void Push(RpnNodeSave *L, DateType data){
  RpnNode *node, *top;
 
  top = L->top;
 
  node = (RpnNode *)malloc(sizeof(RpnNode));
  node->data = data;
  node->next = top;
 
  L->top = node;
  L->count++;
}
 
// 出站
void Pop(RpnNodeSave *ptr, DateType *e){
  RpnNode *node, *topnext;
 
  node = ptr->top;
  *e = node->data;
  topnext = node->next;
 
  free(node);
 
  ptr->top = topnext;
  ptr->count--;
}
 
// 打印值
void printStack(RpnNode *L){
  while(L->next){
    printf("%f->", L->data);
    L = L->next;
  }
 
  printf("\n");
}
 
int main(int argc, char const *argv[])
{
  /* code */
  char data;
  char str[10];
  int i = 0;
 
  DateType start, end, store, result;
 
  RpnNode *stractHead;
  stractHead = (RpnNodeList)malloc(sizeof(RpnNode));
  stractHead->next = NULL;
 
  RpnNodeSave *stractPtr;
  stractPtr = (RpnNodeSave *)malloc(sizeof(RpnNodeSave));
  stractPtr->top = stractHead;
  stractPtr->count = 0;
 
  printf("请输入一串后缀表达式, 以Enter结束: \n");
  scanf("%c", &data);
  while(data != '\n'){
 
 
    while(isdigit(data) || '.' == data){
      str[i++] = data;
      str[i] = '\0';
      if (i >= 10){
        printf("输入的单个数据过大\n");
        return -1;
      }
 
      scanf("%c", &data);
      if(' ' == data){
        store = atof(str);
 
        Push(stractPtr, store);
        i = 0;
        break;
      }
    }
 
    switch(data){
      case '+':
        Pop(stractPtr, &end);
        Pop(stractPtr, &start);
 
        Push(stractPtr, start + end);
        break;
      case '-':
        Pop(stractPtr, &end);
        Pop(stractPtr, &start);
 
        Push(stractPtr, start - end);
        break;
      case '*':
        Pop(stractPtr, &end);
        Pop(stractPtr, &start);
 
        Push(stractPtr, start * end);
        break;
      case '/':
        Pop(stractPtr, &end);
        Pop(stractPtr, &start);
 
        if(end == 0){
          printf("输入错误,除数不能为0\n");
          return -1;
        }
        Push(stractPtr, start / end);
        break;
    }
    scanf("%c", &data);
  }
 
  Pop(stractPtr, &result);
  printf("result: %f \n", result);
 
  getchar();
  return 0;
}
 

如有帮助，望采纳！谢谢!