📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5578| 回复: 9
跳转到指定楼层
上一主题 下一主题
收起左侧

[高频题] 计算器类

全局:
高频题
公司名称: google

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x


逆波兰

您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies



评分

参与人数 1大米 +1 收起 理由
bendd + 1 很有用的信息!

查看全部评分


上一篇:围棋
下一篇:matrix里的路径和必经点问题

本帖被以下淘专辑推荐:

Warald 2019-3-8 06:15:57 | 只看该作者
全局:
关于双倍积分奖励算法题和系统设计题讨论的决定:

我们:
1. 希望能看到干货讨论;
2. 希望能看到好的代码(web端高级发帖模式下,@ 朋友右边的<> 可以选择多种代码)

版主 @14417335 负责审核加分,也请大家给好的回复加分 + 顶。
大家给30,我会跟进奖励30,double之;
大家给100,我也会跟进奖励100,double之。

很理解大家写代码、调试、写思路分析,很花时间。对于特别好的回复,还会有额外加分。

欢迎大家拿出好的题目讨论,选中了我会全站置顶。哪位同学起了好的题目/帖子,激发了干货讨论,也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复,也请大家顶一下,作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目:

在刷题版里选择高频题标签,版主@14417335 发的所有帖子,链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019


回复

使用道具 举报

全局:
wiki了一下shunting yard algorithm和operator precedence parser
记得g4g上也有专题
回复

使用道具 举报

🔗
aizhongren 2019-3-8 14:10:03 | 只看该作者
本楼:
全局:
点个赞!!!!!
回复

使用道具 举报

全局:
对呀!用stack做。
^优先级最高

评分

参与人数 1大米 +1 收起 理由
14417335 + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
bendd 2019-3-8 17:07:13 | 只看该作者
全局:
中序表达式转后序表达式,优先级大家都知道要注意,从低到高就是 +- ,*/ ,^ ,(。
而后要注意^是右结合的,2^2^3=256,a^b^c->abc^^;但普通加减法是左结合的3-2-1=0->32-1-而不是321--。
思路:
维护一个堆栈S存放操作符。def 符号出栈:从符号栈顶移除并输出,如果是括号不必输出。
遍历中序表达式:
  遇到变量输出
  遇到符号与栈顶符号比较
    如果是左括号强制压栈,是右括号则符号出栈直到弹出一个左括号。
    如果优先级高于栈顶的,压栈,注意连续的指数符号视作高于关系。
    否则优先级低于栈顶,则符号出栈直到遇到左括号或优先级更低的。
遍历完表达式 栈内所有符号出栈。

补充内容 (2019-3-8 19:42):
代码在楼下,新人求米,谢谢各位大佬~

评分

参与人数 1大米 +30 收起 理由
14417335 + 30 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
bendd 2019-3-8 19:37:14 | 只看该作者
全局:
Python3 的代码 主要体现思路 没有处理奇怪的case

  1. opPr = {'+': 0, '-': 0, '*': 1, '/': 1, '^': 2, '(': 9}
  2. class Op:
  3.     # used to store operator and compare priority
  4.     def __init__(self, x):
  5.         self.op = x
  6.         self.val = opPr[x]

  7.     def __gt__(self, other):
  8.         return self.val > other.val

  9.     def __ge__(self, other):
  10.         return self.val >= other.val


  11. def infix2Postfix(exp):
  12.     stack = []
  13.     for c in exp:
  14.         if c.isalnum():
  15.             print(c, end='')  # print letter or num directly
  16.             continue
  17.         if c == '(':
  18.             stack.append(Op(c))  # push '(' directly
  19.             continue
  20.         if c == ')':
  21.             # pop until a left '('
  22.             while stack[-1].op != '(':
  23.                 print(stack.pop().op, end='')
  24.             stack.pop()  # pop a '('
  25.             continue

  26.         # process operators
  27.         if len(stack) == 0 or stack[-1].op == '(':
  28.             # top of the stack is empty or '('
  29.             stack.append(Op(c))
  30.             continue
  31.         if Op(c) > stack[-1] or (c == '^' and stack[-1].op == '^'):
  32.             # current operator is prior
  33.             stack.append(Op(c))
  34.             continue

  35.         # top of stack's operator is prior
  36.         while len(stack) > 0 and stack[-1].op != '(' and stack[-1] >= Op(c):
  37.             print(stack.pop().op, end='')
  38.         stack.append(Op(c))

  39.     # infix expression is all traversed
  40.     while len(stack)>0:
  41.         c = stack.pop().op
  42.         if c == '(':
  43.             continue
  44.         print(c, end='')

  45. def main():
  46.     import sys

  47.     def readlines():
  48.         for line in sys.stdin:
  49.             yield line.strip('\n')

  50.     lines = readlines()
  51.     while True:
  52.         try:
  53.             line = next(lines)
  54.             infix2Postfix(line)
  55.             print()
  56.         except StopIteration:
  57.             break


  58. if __name__ == '__main__':
  59.     main()

复制代码
附一些测试用例:
a-b-c
a+b*c+d
a+b*(c+d)
a+b*(c+d^e^f)/g-h*i
(a+b*c+(d*e^f+h))


相应输出:
ab-c-
abc*+d+
abcd+*+
abcdef^^+*g/+hi*-
abc*+def^*h++


可以去leetcode的playground上直接跑。

评分

参与人数 2大米 +120 收起 理由
admin + 60
14417335 + 60 相应输出点个赞!方便其它同学理解

查看全部评分

回复

使用道具 举报

🔗
yuqinlear 2019-3-8 22:16:33 | 只看该作者
全局:
核心就是用一个栈储存符号,当前符号跟栈顶比较,优先级高的输出,低的入栈。
其余就是两个corner cases,1.括号间清空,2. ^既然要右结合那后来的优先级更高,所以先等下再输出。
求米。

  1. public class PolishNotation {

  2.   public static final Map<Character, Integer> precedenceMap = new HashMap<>();

  3.   static {
  4.     precedenceMap.put('+', 0);
  5.     precedenceMap.put('-', 0);
  6.     precedenceMap.put('*', 1);
  7.     precedenceMap.put('/', 1);
  8.     precedenceMap.put('^', 2);
  9.     precedenceMap.put('(', 99);
  10.     precedenceMap.put(')', 99);
  11.   }

  12.   public String infix2RPN(char[] tokens) {
  13.     StringBuilder sb = new StringBuilder();
  14.     Stack<Character> stack = new Stack();

  15.     for (char token : tokens) {
  16.       Integer currentPrecedence = precedenceMap.get(token);
  17.       if (currentPrecedence == null) {  // 数字直接输出
  18.         sb.append(token);
  19.       } else if (stack.empty()) { // 空栈直接压栈
  20.         stack.push(token);
  21.       } else if (token == ')') { // 括号间所有符号出栈
  22.         while (stack.peek() != '(') {
  23.           sb.append(stack.pop());
  24.         }
  25.         stack.pop();
  26.       } else if (token == '^') { // 特殊情况,右结合先压栈
  27.         stack.push(token);
  28.       } else { // 所有栈内高优先级(包括同等优先)出栈
  29.         while (!stack.empty() && stack.peek() != '(' && precedenceMap.get(stack.peek()) >= currentPrecedence) {
  30.           sb.append(stack.pop());
  31.         }
  32.         stack.push(token);
  33.       }
  34.     }
  35.     // 输出栈内剩余
  36.     while (!stack.empty()) {
  37.       sb.append(stack.pop());
  38.     }

  39.     return sb.toString();
  40.   }

  41. }
复制代码

补充内容 (2019-3-8 22:19):
为什么我也用了代码编辑器,显示的格式这么差?

补充内容 (2019-3-8 22:20):
加了上条补充内容显示又正常了,感觉有点buggy。

评分

参与人数 3大米 +123 收起 理由
admin + 60
bendd + 3 给你点个赞!
14417335 + 60 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
ethan1987 2019-5-14 15:26:18 | 只看该作者
全局:
  1. from collections import deque
  2. def postfix(s):
  3.     tokens = deque(s)
  4.    
  5.     ans = []

  6.     def parse(tokens):
  7.         stack = []
  8.         while tokens:
  9.             x = tokens.popleft()
  10.             if x in '+-':
  11.                 while stack and stack[-1] in '+-*/^': ans.append(stack.pop())
  12.                 stack.append(x)
  13.             elif x in '*/':
  14.                 while stack and stack[-1] in '*/^': ans.append(stack.pop())
  15.                 stack.append(x)
  16.             elif x == '^': # special: right combining
  17.                 stack.append(x)
  18.             elif x == '(':
  19.                 parse(tokens)
  20.             elif x == ')':
  21.                 while stack: ans.append(stack.pop())
  22.                 return
  23.             else: # variable
  24.                 ans.append(x)
  25.         while stack: ans.append(stack.pop())
  26.     parse(tokens)
  27.     return ''.join(ans)

  28. print(postfix('a-b-c')) # ab-c-
  29. print(postfix('a+b*c+d')) # abc*+d+
  30. print(postfix('a+b*(c+d)')) # abc^^
  31. print(postfix('a^b^c')) # abc^^
  32. print(postfix('a^b^c+d')) # abc^^d+
  33. print(postfix('a+b^c^d')) # abcd^^+
  34. print(postfix('a+b^c^d+e')) # abcd^^+e+
  35. print(postfix('a+b*(c+d^e^f)/g-h*i')) # abcdef^^+*g/+hi*-
  36. print(postfix('a+b*c+(d*e^f+h)')) # abc*+def^*h++
复制代码
回复

使用道具 举报

🔗
ethan1987 2019-5-14 15:27:19 | 只看该作者
全局:
  1. from collections import deque
  2. def postfix(s):
  3.     tokens = deque(s)
  4.    
  5.     ans = []

  6.     def parse(tokens):
  7.         stack = []
  8.         while tokens:
  9.             x = tokens.popleft()
  10.             if x in '+-':
  11.                 while stack and stack[-1] in '+-*/^': ans.append(stack.pop())
  12.                 stack.append(x)
  13.             elif x in '*/':
  14.                 while stack and stack[-1] in '*/^': ans.append(stack.pop())
  15.                 stack.append(x)
  16.             elif x == '^': # special: right combining
  17.                 stack.append(x)
  18.             elif x == '(':
  19.                 parse(tokens)
  20.             elif x == ')':
  21.                 while stack: ans.append(stack.pop())
  22.                 return
  23.             else: # variable
  24.                 ans.append(x)
  25.         while stack: ans.append(stack.pop())
  26.     parse(tokens)
  27.     return ''.join(ans)

  28. print(postfix('a-b-c')) # ab-c-
  29. print(postfix('a+b*c+d')) # abc*+d+
  30. print(postfix('a+b*(c+d)')) # abc^^
  31. print(postfix('a^b^c')) # abc^^
  32. print(postfix('a^b^c+d')) # abc^^d+
  33. print(postfix('a+b^c^d')) # abcd^^+
  34. print(postfix('a+b^c^d+e')) # abcd^^+e+
  35. print(postfix('a+b*(c+d^e^f)/g-h*i')) # abcdef^^+*g/+hi*-
  36. print(postfix('a+b*c+(d*e^f+h)')) # abc*+def^*h++
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表