使用Java的递归表达式求值程序

Question

我打算写一个表达式求值器,它只进行加法和减法.我有一个简单的算法来做到这一点; 但是,我有一些实施问题.

我认为表达式为(它是一个字符串)

"(" <expression1> <operator> <expression2> ")"

这是我的算法

String evaluate( String expression )

   if expression is digit
      return expression

   else if expression is "(" <expression1> <operator> <expression2> ")"
      cut the brackets out of it
      expression1 = evaluate( <expression1> )
      operator = <operator>
      expression2 = evaluate( <expression2> )

   if operator is +
      expression1 + expression2

   else if operator is -
      expression1 - expression2 

我的问题是解析<expression1>,<operator>并<expression2>从表达.我怎样才能做到这一点？

注意:我不是要求代码.我需要的只是一个想法.

谢谢,

-Ali

Answer 1

我的问题是从表达式解析<expression1>,<operator>和<expression2>

不要这样做,然后:)当你看到一个左括号时,你做递归调用表达式.在表达结束时,要么你找到另一个运算符(所以你毕竟不是在表达式的末尾),或者右括号,在这种情况下你从评价中返回.