C语言重构【150】逆波兰表达式求值

川长思鸟来 2023-02-14 02:16 31阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：栈
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

根据逆波兰表示法，求表达式的值。
    
    有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
    
    说明：
    
    整数除法只保留整数部分。
    给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
    示例 1：
    
    输入: ["2", "1", "+", "3", "*"]
    输出: 9
    解释: ((2 + 1) * 3) = 9
    示例 2：
    
    输入: ["4", "13", "5", "/", "+"]
    输出: 6
    解释: (4 + (13 / 5)) = 6
    示例 3：
    
    输入: ["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

#### 方案：栈 ####

*  [Java版][Java]

int evalRPN(char ** tokens, int tokensSize){ 
        int* pStack = (int*)malloc(tokensSize * sizeof(int));
        int top = -1;
        int row = 0;
        int left = 0;
        int right = 0;
    
        for (row = 0; row <= tokensSize - 1; row++)
        { 
            if ('+' == tokens[row][0])
            { 
                right = pStack[top--]; // pop
                left = pStack[top--]; // pop 
                pStack[++top] = left + right; // push
            }
            else if ('-' == tokens[row][0] && '\0' == tokens[row][1]) // 负数
            { 
                right = pStack[top--]; // pop
                left = pStack[top--]; // pop 
                pStack[++top] = left - right; // push
            }
            else if ('*' == tokens[row][0])
            { 
                right = pStack[top--]; // pop
                left = pStack[top--]; // pop
                pStack[++top] = left * right; // push
            }
            else if ('/' == tokens[row][0])
            { 
                right = pStack[top--]; // pop
                left = pStack[top--]; // pop
                pStack[++top] = left / right; // push
            }
            else // number
            { 
                pStack[++top] = atoi(tokens[row]); // push
            }
        }
    
        return pStack[top]; // peek
    }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[Java]: https://blog.csdn.net/symuamua/article/details/106449457