后缀符号验证?
评估包含后缀表达式(例如:3 5 +)的字符串(数组,某些东西)以检查有效性的好方法是什么?
What would be a good way to evaluate a string(array, something) that contains a postfix expression(ex: 3 5 +) to check for validity?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
我在这里假设您所说的“有效”的意思是执行代码永远不会使堆栈下溢,并且会在堆栈上留下单个值。 如果您对有效性有更严格的概念,则需要更复杂的检查器。
如果要检查这种有效性,则无需评估字符串,并且可以使用计数器,而不是堆栈。 如果您进行计算,计数器会跟踪堆栈上的值的数量。 为了简单起见,我们假设您只有文字、二元运算符和一元运算符。 此算法使用特殊的递减操作:如果递减时计数器低于零,则字符串无效:
I'm assuming here that what you mean by valid is that executing the code will never underflow the stack and will leave a single value on the stack. If you have a more stringent notion of validity, you'll need a more sophisticated checker.
If you want to check for this kind of validity, it is not necessary to evaluate the string, and you can use a counter, not a stack. The counter tracks the number of values that would be on the stack if you evaluated. To simplify, let's suppose you have only literals, binary operators, and unary operators. This algorithm uses a special decrement operation: if when you decrement, the counter goes below zero, the string is invalid:
后缀表达式有效当且仅当:
1) 前两个元素是操作数(值),并且
2) 最后一个元素是运算符,并且
3) 对于每 n 个值,有 n-1 个运算符,并且
4) 在 n 个元素的列表中,从索引 i = 0 开始,因为 i < n-1(倒数第二个元素),每组元素由 k 个值组成(对于 k > 1 ),后面跟着 (k-1) 个运算符。 当 k = 1 时,后面的运算符数量 = k = 1。
A postfix expression is valid if and only if:
1) The first two elements are operands(values), and
2) The last element is an operator, and
3) For every n values there are n-1 operator(s), and
4) In a list of n elements, starting at index i = 0 for i < n-1 (the second to last element), every group of elements consisting of k values( for k > 1 ) is followed by (k-1) operators. When k = 1, the number of operators that follows = k = 1.
算法:维护一个堆栈并扫描
后缀表达式从左到右
– 如果元素是数字,则将其压入
堆
– 如果元素是运算符O,则弹出两次
并分别得到A和B。 计算
BOA并将其推回堆栈
– 当表达式结束时,数字
堆栈中是最终答案
//为了有效性 如果堆栈中只剩下一个数字,则其正确表达式
//如果堆栈中留下多个数字并且没有运算符,则其错误
//如果您有一个或堆栈和运算符中没有数字,那么它是错误的
Algorithm: maintain a stack and scan the
postfix expression from left to right
– If the element is a number, push it into the
stack
– If the element is a operator O, pop twice
and get A and B respectively. Calculate
BOA and push it back to the stack
– When the expression is ended, the number
in the stack is the final answer
//For validity If you are left with only one number in Stack its correct expression
//If you are left with more than one number in stack and no operator then its wrong
//If you have one or no number in stack and operators left then its wrong
检查后缀表达式是否有效:(如果输入在字符数组中)
1.操作数的个数必须等于no。 运算符 + 1。
要检查这一点,请保留一个检查变量。
检查=0。 对于每个操作数递增该值,对于每个运算符递减该值。如果最终其值为 1,则表达式有效。
2.数组的前2个元素必须是操作数。后缀表达式不能将运算符作为第一个或第二个元素。
通过 if 控制语句检查这一点。
To check if a postfix expression is valid or not:(if input is in char array)
1.Number of operands must equal no. of operators + 1.
To check this keep a check variable.
check=0. Increment this for every operand and decrement for each operator.If finally its value is 1,then expression is valid.
2.The first 2 elements of the array need to be operands.No postfix expression can have operator as 1st or 2nd element.
Check this by if control statement.