从中缀到前缀的转换 [英] conversion from infix to prefix
本文介绍了从中缀到前缀的转换的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正准备考试,对于以下表达式,我无法理解中缀表示法到波兰表示法的转换:
I am preparing for an exam where i couldn't understand the convertion of infix notation to polish notation for the below expression:
(a–b)/c*(d + e – f / g)
可以一步一步讲给定的表达式将如何转换为前缀?
Can any one tell step by step how the given expression will be converted to prefix?
推荐答案
Algorithm ConvertInfixtoPrefix
Purpose: Convert an infix expression into a prefix expression. Begin
// Create operand and operator stacks as empty stacks.
Create OperandStack
Create OperatorStack
// While input expression still remains, read and process the next token.
while( not an empty input expression ) read next token from the input expression
// Test if token is an operand or operator
if ( token is an operand )
// Push operand onto the operand stack.
OperandStack.Push (token)
endif
// If it is a left parentheses or operator of higher precedence than the last, or the stack is empty,
else if ( token is '(' or OperatorStack.IsEmpty() or OperatorHierarchy(token) > OperatorHierarchy(OperatorStack.Top()) )
// push it to the operator stack
OperatorStack.Push ( token )
endif
else if( token is ')' )
// Continue to pop operator and operand stacks, building
// prefix expressions until left parentheses is found.
// Each prefix expression is push back onto the operand
// stack as either a left or right operand for the next operator.
while( OperatorStack.Top() not equal '(' )
OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand
OperandStack.Push(operand)
endwhile
// Pop the left parthenses from the operator stack.
OperatorStack.Pop(operator)
endif
else if( operator hierarchy of token is less than or equal to hierarchy of top of the operator stack )
// Continue to pop operator and operand stack, building prefix
// expressions until the stack is empty or until an operator at
// the top of the operator stack has a lower hierarchy than that
// of the token.
while( !OperatorStack.IsEmpty() and OperatorHierarchy(token) lessThen Or Equal to OperatorHierarchy(OperatorStack.Top()) )
OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand
OperandStack.Push(operand)
endwhile
// Push the lower precedence operator onto the stack
OperatorStack.Push(token)
endif
endwhile
// If the stack is not empty, continue to pop operator and operand stacks building
// prefix expressions until the operator stack is empty.
while( !OperatorStack.IsEmpty() ) OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand
OperandStack.Push(operand)
endwhile
// Save the prefix expression at the top of the operand stack followed by popping // the operand stack.
print OperandStack.Top()
OperandStack.Pop()
End
这篇关于从中缀到前缀的转换的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文