大厂秋招真题【栈】Bilibili2019秋招-简单表达式求值

题目描述与示例

题目描述

给定一个合法的表达式字符串，其中只包含非负整数、加法、减法以及乘法符号（不会有括号），例如7+3*4*5+2+4-3-1，请写程序计算该表达式的结果并输出

输入描述

输入有多行，每行是一个表达式，输入以END作为结束

输出描述

每行表达式的计算结果

示例

输入

7+3*4*5+2+4-3-1
2-3*1
END

输出

69
-1

解题思路

本题属于经典的中缀表达式计算类栈题，但相比起LeetCode上的几道类似题目相对简单。

代码

Python

# 题目：【栈】Bilibili2019秋招-简单表达式求值
# 作者：闭着眼睛学数理化
# 算法：栈
# 代码有看不懂的地方请直接在群上提问# 更新栈的函数
def update_stack(stack, preSign, num):# 如果前一个符号为乘号，则将栈顶元素乘以numif preSign == "*":stack[-1] *= num# 如果前一个符号为减号，则将-num压入栈中elif preSign == "-":stack.append(-num)# 如果前一个符号为加号，则将num压入栈中elif preSign == "+":stack.append(num)return# 表达式求值的核心函数
def cal_res(line):# 初始化一个空栈stack = list()# 初始化上一个遇到的符号preSign为加号preSign = "+"# 初始化遍历过程中遇到的数字num为0num = 0for ch in line:# 遇到数字的情况，更新numif ch.isdigit():num = num * 10 + int(ch)# 遇到符号（+、-或*）的情况else:# 需要根据num和之前的符号preSign更新栈update_stack(stack, preSign, num)# num已经用完，需要重新将其赋值为0num = 0# 此时的ch赋值给preSign，留着下次使用preSign = ch# 最后一个num尚未计算过，故还需再次调用update_stack()函数update_stack(stack, preSign, num)# 对整个栈进行求和，即为最终的计算结果return sum(stack)line = input()
ans = list()
# 反复输入line，直到输入END
while line != "END":ans.append(cal_res(line))line = input()for res in ans:print(res)

Java

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);List<Long> ans = new ArrayList<>();String line = scanner.nextLine();while (!line.equals("END")) {ans.add(calRes(line));line = scanner.nextLine();}for (long res : ans) {System.out.println(res);}}static long calRes(String line) {List<Long> stack = new ArrayList<>();char preSign = '+';long num = 0;for (char ch : line.toCharArray()) {if (Character.isDigit(ch)) {num = num * 10 + Character.getNumericValue(ch);} else {updateStack(stack, preSign, num);num = 0;preSign = ch;}}updateStack(stack, preSign, num);long result = 0;for (long numInStack : stack) {result += numInStack;}return result;}static void updateStack(List<Long> stack, char preSign, long num) {if (preSign == '*') {stack.set(stack.size() - 1, stack.get(stack.size() - 1) * num);} else if (preSign == '-') {stack.add(-num);} else if (preSign == '+') {stack.add(num);}}
}

C++

#include <iostream>
#include <vector>using namespace std;void updateStack(vector<long long> &stack, char preSign, long long num) {if (preSign == '*') {stack.back() *= num;} else if (preSign == '-') {stack.push_back(-num);} else if (preSign == '+') {stack.push_back(num);}
}long long calRes(string line) {vector<long long> stack;char preSign = '+';long long num = 0;for (char ch : line) {if (isdigit(ch)) {num = num * 10 + (ch - '0');} else {updateStack(stack, preSign, num);num = 0;preSign = ch;}}updateStack(stack, preSign, num);long long result = 0;for (long long numInStack : stack) {result += numInStack;}return result;
}int main() {vector<long long> ans;string line;while (true) {getline(cin, line);if (line == "END") {break;}ans.push_back(calRes(line));}for (long long res : ans) {cout << res << endl;}return 0;
}

时空复杂度

时间复杂度：O(Nt)。字符串line中的每一个元素仅需遍历一次。t为询问次数。

空间复杂度：O(N)。栈所占空间。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多