LeetCode 面试题 16.26. 计算器

一、题目

  给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

  表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

输入: “3+2*2”
输出: 7

示例 2:

输入: " 3/2 "
输出: 1

示例 3:

输入: " 3+5 / 2 "
输出: 5

说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

  点击此处跳转题目。

二、C# 题解

  首先将中缀表达式转换为后缀表达式，然后计算后缀表达式：

public class Solution {public int Calculate(string s) {ArrayList   post   = new ArrayList();   // 后缀表达式Stack<char> opStk  = new Stack<char>(); // 操作符栈Stack<int>  numStk = new Stack<int>();  // 操作数栈int         num    = 0;                 // 存储每次扫描的数字/* 生成后缀表达式 post */foreach (char c in s) {if (char.IsNumber(c)) num = num * 10 + c - '0'; // 碰见操作数else if (c != ' ') {                            // 碰见操作符post.Add(num);num = 0;while (opStk.Count != 0 && OpPriority(opStk.Peek(), c) >= 0) // 将优先级不低于 c 的操作符弹入 postpost.Add(opStk.Pop());opStk.Push(c); // c 进栈}}post.Add(num);                                  // 最后一个操作数进栈while (opStk.Count != 0) post.Add(opStk.Pop()); // 剩余操作符进栈/* 计算后缀表达式 post */foreach (object o in post) {if (o is char c) {// 每次取出两个操作数int n2 = numStk.Pop();int n1 = numStk.Pop();// 计算结果，压入栈内int result = c switch {'+' => n1 + n2,'-' => n1 - n2,'*' => n1 * n2,'/' => n1 / n2,_   => 0};numStk.Push(result);}else numStk.Push((int)o);}return numStk.Pop();}// 比较 c1 和 c2 的优先级// c1 > = < c2 分别返回 1 0 -1public int OpPriority(char c1, char c2) => c1 switch {'*' or '/' when c2 is '*' or '/' => 0,'*' or '/'                       => 1,'+' or '-' when c2 is '+' or '-' => 0,'+' or '-'                       => -1,};
}

• 时间：68 ms，击败 71.43% 使用 C# 的用户
• 内存：44.35 MB，击败 28.57% 使用 C# 的用户

---

  对于本题，由于只有两个优先级的操作符，因此可以简化操作：

public class Solution {public int Calculate(string s) {Stack<int> numStk = new Stack<int>();int        ans    = 0, num = 0;char       preOp  = '+'; // 上次的操作符for (int i = 0; i < s.Length; i++) {if (char.IsNumber(s[i])) num = num * 10 + s[i] - '0';if (!char.IsNumber(s[i]) && s[i] != ' ' || i == s.Length - 1) { // 遇见操作符或者到达结尾switch (preOp) { // 依据上一个操作符计算结果放入 numStk 中case '+':numStk.Push(num);break;case '-':numStk.Push(-num);break;case '*':numStk.Push(numStk.Pop() * num);break;case '/':numStk.Push(numStk.Pop() / num);break;}num = 0;preOp = s[i];}}while (numStk.Count != 0) ans += numStk.Pop(); // 结果累加return ans;}
}

• 时间：56 ms，击败 100.00% 使用 C# 的用户
• 内存：37.93 MB，击败 57.14% 使用 C# 的用户