Когда я написал эту статью о вычислении инфиксного выражения, состоящего из нескольких цифр, мне было лень делать это для выражений в скобках. Итак, вот оно.
Как обычно, вот версия javascript .
Так же, как и без парантезированной версии, этот алгоритм представляет собой алгоритм двух стеков, модифицированный для размещения скобок и нескольких цифр . Плавающие точки не поддерживаются намеренно и не проверяются. Однако я не вижу причин, по которым он не должен работать (при условии, что вы меняете типы переменных для размещения числа с плавающей запятой).
Алгоритм выглядит так:
1. Initialize two stacks - one for holding values and one for holding operators
2. Read the input expression from left to right - one character at a time.
3. If the character is a space, ignore
4. If the character is a number, then append it to an accumulating variable
(don't push it to the stack yet)
5. If the character is an operator or a right parenthesis, push the accumulated number
to the value stack and reinitialize the accumulator.
5a. If the current operator is a left parenthesis, push it to the expression stack
and continue to the next character in the expression.
5b. If the current operator is a right parenthesis, then evaluate the stacks
until the first left parenthesis is reached. Push the result back to the value stack
5b. If the current operator is of higher precedence than the first item in the operator stack,
then safely ignore and read further.
5c. If the current operator is of lower precedence than the first item in the operator
stack (peek view), then evaluate the previous set (two from value stack and one
from operator stack) and insert the result into the value stack
5d. Finally, insert the current operator to the operator stack
Примечание: уровень оператора для правой круглой скобки сохраняется на «0», чтобы сохранить приоритет оператора, в то время как уровень оператора для левого паратеза сохраняется на «3» (или что-либо выше, чем у всех операторов), чтобы быть наименьшим в приоритете. Единственная цель сохранения левых скобок в стеке выражений состоит в том, чтобы идентифицировать начало искаженного подвыражения.
public static final Map OPERATOR_LEVELS= [")":0, "*":1, "/":1, "+":2,"-":2, "(":3]
Groovy реализация здесь:
/**
* Only basic arithmetic operators are supported. However, could easily be
* extended to support any binary operators
*
* This program is not an infix to postfix converter. However, this program does the following
*
* 1) Evaluates a parenthesized or non-parenthesized infix expression and drives it to a final value
* 2) Supports parentheses
* 3) Supports multiple digits as operands
* 4) Empty space allowed
* 5) Floating point numbers not supported by intent
* 6) Supports only the 4 basic arithmetic operators but could easily be extended to support any other
* binary operation
*
* @author Arun Manivannan
*/
public class InfixToValueParenthesis {
public static final String OPERATORS="+-/*()" //ignore the "(" as an operator
public static final Map OPERATOR_LEVELS= [")":0, "*":1, "/":1, "+":2,"-":2, "(":3]
public static void main(String[] args) {
String inputExpression="((10 - 5)*(3+6))*2+3" //610
InfixToValueParenthesis ifixToPfix=new InfixToValueParenthesis()
ifixToPfix.infixToValue(inputExpression);
}
def infixToValue(String inputExpression) {
Stack<String> expressionStack = new Stack<String>()
Stack<Long> valueStack = new ArrayDeque<Long>() //to hold only non-decimal values
String eachNumber="" //to hold multiple digit values. lame idea, i know, but can't think of anything else at 2 AM
int totalCharInInput=inputExpression.length()
inputExpression.each { eachChar->
totalCharInInput--
println ("each char : "+eachChar)
if (eachChar.trim()==""){
//ignore
}
else if (isValidOperator(eachChar)){
//We could stack up a lot of left parenthesis in the beginning without reaching a number. Weed it out
if (!isLeftParen(eachChar) && eachNumber.isNumber()){
valueStack.push(Long.parseLong(eachNumber)) //push the till now accumulated number to the value stack
eachNumber=""
}
if (expressionStack.isEmpty() || isLeftParen(eachChar)){ //first item or left parenthesis
expressionStack.push(eachChar)
}
else if (isRightParen(eachChar)){
evaluateAndPushValueToStackUntilLeftParenthesis(valueStack, expressionStack)
}
//if the current operator has higher precedence than the first item in the stack, then it is fine.
//Just insert the incoming
else if (getHigherPrecedenceOperator(eachChar, expressionStack.peek())==eachChar){
expressionStack.push(eachChar)
}
//if the current operator is lesser, then the previous higher precedence expression have to be
//evaluated. Else, we would be making wrong calculations while popping off for final evaluation
else{
//the current operator has higher precedence. Evaluate expression
evaluateAndPushValueToValueStack(valueStack, expressionStack)
//after evaluation of the higher pair, don't forget to insert the current character into the expression stack
expressionStack.push(eachChar)
}
}
else if (eachChar.isNumber()){
eachNumber+=eachChar
if (totalCharInInput==0){
valueStack.push(Long.parseLong(eachNumber)) //the last element
}
}
/*else {
//other input (alphabets and special chars) are treated as garbage
}*/
println ("Value Stack : "+valueStack)
println ("Expression Stack : "+expressionStack)
}
println ("Final Expression stack " +expressionStack);
println ("Final Value stack : "+valueStack)
while (!expressionStack.empty){
evaluateAndPushValueToValueStack(valueStack,expressionStack)
}
println ("Final value : "+valueStack)
}
boolean isRightParen(String operator) {
operator==")"?true:false
}
boolean isLeftParen(String operator) {
operator=="("?true:false
}
private void evaluateAndPushValueToValueStack(Stack<Long> valueStack, Stack<String> expressionStack) {
Long firstOperand=valueStack.pop()
Long secondOperand=valueStack.pop()
println ("Value stack : "+firstOperand+ ":"+ secondOperand )
Long evaluatedValue = this.evaluate(secondOperand, firstOperand, expressionStack.pop()) //intermediate result
valueStack.push(evaluatedValue)
}
private void evaluateAndPushValueToStackUntilLeftParenthesis(Stack<Long> valueStack, Stack<String> expressionStack) {
while (!expressionStack.empty){
if (isLeftParen(expressionStack.peek())){ //if the left parenthesis has been reached, then pop it up and exit
expressionStack.pop()
break
}
evaluateAndPushValueToValueStack(valueStack,expressionStack)
}
}
Long evaluate(Long firstOperand, Long secondOperand, String operator) {
Long returnValue
switch (operator) {
case "+" :
returnValue=firstOperand+secondOperand
break
case "-" :
returnValue=firstOperand-secondOperand
break;
case "*":
returnValue=firstOperand*secondOperand
break
case "/":
if (secondOperand==0){ //cheating death by zero
returnValue=0
}
else{
returnValue=firstOperand/secondOperand
}
break;
}
}
boolean isValidOperator(String input) {
OPERATORS.contains(input)?true:false
}
String getHigherPrecedenceOperator(String firstOperator, String secondOperator){
OPERATOR_LEVELS[firstOperator]<OPERATOR_LEVELS[secondOperator]?firstOperator:secondOperator
}
}