给定一个算术表达式字符串，找到该表达式的十进制值。
一道面试题。
给定一个算术表达式字符串，找到该表达式的十进制值。
例如。给出
30*(5+10) is a string, its value is 450.
我的想法：
一一解析每个符号，并将字符串重建为具有运算符优先级的表达式。但是，它效率不高，是 O(n^2) 甚至更糟。
更好的想法？
谢谢
An interview question.
Given a string of arithmetic expression, find the decimal value of the expression.
e.g . given
30*(5+10) is a string, its value is 450.
My idea:
parse each symbol one by one and rebuild the string as an expression with priority of operators. But, it is not efficient, it is O(n^2) or even worse.
Better ideas ?
thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可以使用堆栈在 O(n) 时间内将表达式转换为后缀。
然后在 O(n) 时间内使用堆栈计算后缀表达式。
需要转换为 Postfix 来确定表达式求值期间运算符的优先级。
请参阅使用堆栈计算算术表达式 http://www.cs .wcupa.edu/~rkline/DS/deque-stack-algorithms.html
You can convert the expression into postfix using stack in O(n) time.
Then evaluate the postfix expression with stack in O(n) time.
Converting to Postfix is required for determining the priority of operators during the expression evaluation.
Refer evaluation of arithmetic expressions with stack http://www.cs.wcupa.edu/~rkline/DS/deque-stack-algorithms.html
使用有限状态自动机解析和标记字符串：
整数 ->整数标记
运算符 ->操作员令牌
左括号 ->状态 - 新表达式
右括号 -> state - 关闭表达式
，这样您就可以构建树并通过将树底部压平来执行。
parse and tokenize the string with a finite state automaton:
integer -> integer-token
operator -> operator token
opening-bracket -> state - new expression
closing-bracket -> state - close expression
that way you could just build the tree and execute by flattening the tree bottum up.
用交易术语描述操作：构建或找到算术表达式的解析器，解析字符串，评估抽象语法树（AST）并返回结果。由于算术表达式是上下文无关语言并且在
LL(1)中，因此这在O(n)中是可能的。使用 Boost.Spirit 或 yacc 构建解析器的成本很低。Describe the operation in the terms of the trade: Build or find a parser for arithmetic expressions, parse the string, evaluate the abstract syntax tree (AST) and return the result. Since arithmetic expressions are context-free languages and in
LL(1), this is possible inO(n). Building a parser is cheap with Boost.Spirit oryacc.在用一对额外的括号括起来的表达式之前添加字符串
"print "，在末尾放置一个分号并将其传递给 perl -e，即在 C 中：Prepend the string
"print "before the expression wrapped in an extra pair of parenthesis, put a semicolon at the end and pass it to perl -e, i.e. in C: