珠海市官网网站建设价格,网站建设08keji,怎样添加网站图标,网络推广培训班好吗文章目录 题目描述与示例题目描述输入描述输出描述示例输入输出 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
给定一个合法的表达式字符串#xff0c;其中只包含非负整数、加法、减法以及乘法符号#xff08;不… 文章目录 题目描述与示例题目描述输入描述输出描述示例输入输出 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
给定一个合法的表达式字符串其中只包含非负整数、加法、减法以及乘法符号不会有括号例如73*4*524-3-1请写程序计算该表达式的结果并输出
输入描述
输入有多行每行是一个表达式输入以END作为结束
输出描述
每行表达式的计算结果
示例
输入
73*4*524-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);ListLong 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) {ListLong 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(ListLong 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 vectorusing namespace std;void updateStack(vectorlong 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) {vectorlong 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() {vectorlong 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动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
