石神

V1

2023/03/08阅读:9主题:全栈蓝

【栈与队列】逆波兰表达式求值

逆波兰表达式求值

本文只是节选公众号的中的一篇,我的公众号每日都会更新,欢迎参观 公众号算法每日一更

leetcode链接:https://leetcode.cn/problems/evaluate-reverse-polish-notation/

题目描述:

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

有效的算符为 '+'、'-'、'*' 和 '/' 。 每个操作数(运算对象)都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。

//示例 1:
输入:tokens = ["2","1","+","3","*"]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

//示例 2:
输入:tokens = ["4","13","5","/","+"]
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

//示例 3:
输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出:22
解释:该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
17 + 5
22

提示:

  • 1 <= tokens.length <= 104
  • tokens[i] 是一个算符("+"、"-"、"*" 或 "/"),或是在范围 [-200, 200] 内的一个整数

😒其实就是给了个后缀表达式,让你转中缀表达式并求值。

  • 解法:数组模拟栈
int convert(char* tokens){
    int tag = 1;
    int ret = 0;
    int count = 1;
    for(int i = strlen(tokens) - 1; i >= 0; i--){
        if(tokens[i] == '-'){
            tag = -1;
            break;
        }
        ret += count * (tokens[i] - '0');
        count *= 10;
    }
    return ret * tag;
}

int evalRPN(char ** tokens, int tokensSize){
    int stack[tokensSize];
    int stackTop = 0;
    int num = 0;
    int a = 0, b = 0;
    
    for(int i = 0; i < tokensSize; i++){
        char* token = tokens[i];
        // 判断输入是不是数字
        if(strlen(token) > 1 || (token[0] >= '0' && token[0] <= '9')){
            num = convert(token);
            stack[stackTop++] = num;
        }
  else{
            b = stack[--stackTop];
            a = stack[--stackTop];
            switch (token[0]){
                case '+':{
                    stack[stackTop++] = a + b;
                    break;
                }
                case '-':{
                    stack[stackTop++] = a - b;
                    break;
                }
                case '*':{
                    stack[stackTop++] = a * b;
                    break;
                }
                case '/':{
                    stack[stackTop++] = a / b;
                    break;
                }
            }// switch
        }// else
    }
    return stack[0];
}

其中,convert()函数将字符串转为整型,在c语言中有库函数:int atoi(const char* str),其头文件为#include<stdlib.h>。同时注意一下输入是不是数字的判断方式。

分类:

后端

标签:

后端

作者介绍

石神
V1