请教关于表达式判断的有关问题（给高分）
请问关于表达式判断的问题（给高分）
一个字符串s,只能由+,-,*,/及0~9的数字，还有括号( , )构成，如何判断s是否是一个合法的算术表达式，给出函数实现
------解决方案--------------------
递归下降分析:)
S -> E '\0 '
E -> E op T | T
T -> '( ' E ') ' | num
op -> '+ ' | '- ' | '* ' | '/ '
------解决方案--------------------
确实，如WizardLucien所言, 针对这个问题，使用递归下降分析是比较简单的。而且，不需要很深的编译知识，甚至不需要比一维数组更复杂的数据结构，只要将这些规则逐一实现就可以了。当然，前提是不考虑时空效率，可以多遍或反向地扫描输入字符串（如果不是这样，就必须用到栈，或等效的其他结构。但是即使如此，就此问题而言，二叉树也是不必要的。你可以把分析结果存成二叉树，给后续操作（如语意分析，代码生成等）使用；但本步骤无须树结构，栈已经足够了）。
在多遍情况下（即STL中的forward iterator），本问题的递归下降很简单，每条规则都可以写成一个函数，可用-> 左边的符号表示。每个函数都可以接收一个开始和结束位置（学过STL的话，可用iterator，并至少是一个forward iterator，当然bidirectional iterator性能更佳，random则没有必要，也不会进一步提高性能），也可以是开始位置和长度（这是C中字符串的一般表示法（const char* , size_t））。返回值则是一个bool，表示是否匹配。
第一个式子，S -> E '\0 ' 表示接收的是以 '\0 '结尾的字符串。如果确实是这样，S如下实现：
bool S(const char* str) // 由于不会修改输入，所以全部是const_iterator
{
const char* end = ...// 搜索str中第一个 '/0 '，将该位置赋给end,
// STL中可以用find，直接写的话就是个简单的循环比较
return E(str, end); // 或按上述第二种表示法 return E(str, end-str); 下同，略
}
如果输入不满足以 '\0 '结尾的先验条件，则应该由输入提供结尾位置，如
bool S(const char* str, const char* end)
{
return E(str, end)；
}
这里的const_char*可以是任意的const forward iterator
第二个式子 E -> E op T | T ,实现如下
bool E(const char* begin, const char* end)
{
if ( T(begin, end) )
return true;
else
{
const char* find_begin = begin;
do
{
const char* op_iter = ... //从find_begin找到第一个 '+ ' | '- ' | '* ' | '/ '
// STL中可以用find_if(...,op)
// 直接写的话就是个简单的循环，每个字符都调用op函数做测试
if (op_iter == end)
break; // 因为oper+1已经越界了，不可能是正确的。
// 如果不做这个判断，就会无限左递归了！
if(E(begin, op_iter) && T(op_iter+1, end))
return true;
find_begin = op_iter;
} while(op_iter != end);
return false;
}
}
注意，这里首先测试E，是为了提高效率，因为E op T 要测试op在所有位置的情况，直到匹配为止。注意，在E op T 中，因为每次递归调用E的输入长度都不同（递增直到结尾，结尾的情况直接判false），因此不会出现算法无法结束的问题。
第三个式子T -> '( ' E ') ' | num
bool T(const char* begin, const char* end)
{
return ( num(begin, end)
|| *begin == '( ' && *(end-1) == ') ' && E(begin+1, end-1))
}
这里的递归调用每次都缩短了长度，也不存在算法无法结束的问题。
注意，这里*(end-1)假设是bidirectional iterator，如果只是forward iterator要begin++直到end，并用局部变量记录下前一个位置。
第四个式子op -> '+ ' | '- ' | '* ' | '/ '
bool op(const char* begin, const char* end)
{
return (end-begin==1) && (*begin == '+ ' || ...) // '- ' | '* ' | '/ ' 类似写法，略
}
其实还由关于num式子
num -> [1-9]all_num
all_num -> all_num[0-9]
这个很容易解递归，就是测试每个字符都是数字，且第一个数字不为0.函数原型为
bool num(const char* begin, const char* end);
实现从略.
以上伪码简单地解决了目前的问题。其思想很简单，代价是效率比较低，在二、三式中多遍地递归扫描输入。所以简单性是以效率为代价的。
提高效率的方法是解除左递归，并使用栈保存过去的未匹配状态，如
1。还未与 ') '匹配的 '( '
2。还未按优先级可先期完成的操作。如 a+b*c，当读到a+b时不能将a+b先做，只能放在栈中。而a+b-c当读到‘-’时a+b可以出栈并用其和d来代替了。
// 其实上述的实现没优考虑这一点，如果不仅要检验字符串正确性，还要得到正确的语法树，
// 就必须考虑它，将op分为不同优先级的op1和op2，E和T部分做相应的修改和扩充，列出所有
// 的组合。考虑到它比较琐碎，但难度不大，这里就不赘述了
然后建立规则，当读到某字符（按编译的说法，终结符，而上文的S,E,T,op,num等都是非终结符）应该如何处理。简单的说，上文的算法是一个非终结符一个函数；而现在需要一个终结符对应一个函数，顺序读到某终结符时就调用一次对应的函数。该函数将根据当前栈中的状况做合适的处理(压栈/出栈等)，并返回“匹配/不匹配/错误”。在任何一步中返回“错误”（表示无论后续时什么都不可能正确了。如在没有 '( '的情况下出现了 ') '之类的）则提前终止，结果为“不匹配”；否则继续到结束，以最后一次的返回为最终结果。
一个字符串s,只能由+,-,*,/及0~9的数字，还有括号( , )构成，如何判断s是否是一个合法的算术表达式，给出函数实现
------解决方案--------------------
递归下降分析:)
S -> E '\0 '
E -> E op T | T
T -> '( ' E ') ' | num
op -> '+ ' | '- ' | '* ' | '/ '
------解决方案--------------------
确实，如WizardLucien所言, 针对这个问题，使用递归下降分析是比较简单的。而且，不需要很深的编译知识，甚至不需要比一维数组更复杂的数据结构，只要将这些规则逐一实现就可以了。当然，前提是不考虑时空效率，可以多遍或反向地扫描输入字符串（如果不是这样，就必须用到栈，或等效的其他结构。但是即使如此，就此问题而言，二叉树也是不必要的。你可以把分析结果存成二叉树，给后续操作（如语意分析，代码生成等）使用；但本步骤无须树结构，栈已经足够了）。
在多遍情况下（即STL中的forward iterator），本问题的递归下降很简单，每条规则都可以写成一个函数，可用-> 左边的符号表示。每个函数都可以接收一个开始和结束位置（学过STL的话，可用iterator，并至少是一个forward iterator，当然bidirectional iterator性能更佳，random则没有必要，也不会进一步提高性能），也可以是开始位置和长度（这是C中字符串的一般表示法（const char* , size_t））。返回值则是一个bool，表示是否匹配。
第一个式子，S -> E '\0 ' 表示接收的是以 '\0 '结尾的字符串。如果确实是这样，S如下实现：
bool S(const char* str) // 由于不会修改输入，所以全部是const_iterator
{
const char* end = ...// 搜索str中第一个 '/0 '，将该位置赋给end,
// STL中可以用find，直接写的话就是个简单的循环比较
return E(str, end); // 或按上述第二种表示法 return E(str, end-str); 下同，略
}
如果输入不满足以 '\0 '结尾的先验条件，则应该由输入提供结尾位置，如
bool S(const char* str, const char* end)
{
return E(str, end)；
}
这里的const_char*可以是任意的const forward iterator
第二个式子 E -> E op T | T ,实现如下
bool E(const char* begin, const char* end)
{
if ( T(begin, end) )
return true;
else
{
const char* find_begin = begin;
do
{
const char* op_iter = ... //从find_begin找到第一个 '+ ' | '- ' | '* ' | '/ '
// STL中可以用find_if(...,op)
// 直接写的话就是个简单的循环，每个字符都调用op函数做测试
if (op_iter == end)
break; // 因为oper+1已经越界了，不可能是正确的。
// 如果不做这个判断，就会无限左递归了！
if(E(begin, op_iter) && T(op_iter+1, end))
return true;
find_begin = op_iter;
} while(op_iter != end);
return false;
}
}
注意，这里首先测试E，是为了提高效率，因为E op T 要测试op在所有位置的情况，直到匹配为止。注意，在E op T 中，因为每次递归调用E的输入长度都不同（递增直到结尾，结尾的情况直接判false），因此不会出现算法无法结束的问题。
第三个式子T -> '( ' E ') ' | num
bool T(const char* begin, const char* end)
{
return ( num(begin, end)
|| *begin == '( ' && *(end-1) == ') ' && E(begin+1, end-1))
}
这里的递归调用每次都缩短了长度，也不存在算法无法结束的问题。
注意，这里*(end-1)假设是bidirectional iterator，如果只是forward iterator要begin++直到end，并用局部变量记录下前一个位置。
第四个式子op -> '+ ' | '- ' | '* ' | '/ '
bool op(const char* begin, const char* end)
{
return (end-begin==1) && (*begin == '+ ' || ...) // '- ' | '* ' | '/ ' 类似写法，略
}
其实还由关于num式子
num -> [1-9]all_num
all_num -> all_num[0-9]
这个很容易解递归，就是测试每个字符都是数字，且第一个数字不为0.函数原型为
bool num(const char* begin, const char* end);
实现从略.
以上伪码简单地解决了目前的问题。其思想很简单，代价是效率比较低，在二、三式中多遍地递归扫描输入。所以简单性是以效率为代价的。
提高效率的方法是解除左递归，并使用栈保存过去的未匹配状态，如
1。还未与 ') '匹配的 '( '
2。还未按优先级可先期完成的操作。如 a+b*c，当读到a+b时不能将a+b先做，只能放在栈中。而a+b-c当读到‘-’时a+b可以出栈并用其和d来代替了。
// 其实上述的实现没优考虑这一点，如果不仅要检验字符串正确性，还要得到正确的语法树，
// 就必须考虑它，将op分为不同优先级的op1和op2，E和T部分做相应的修改和扩充，列出所有
// 的组合。考虑到它比较琐碎，但难度不大，这里就不赘述了
然后建立规则，当读到某字符（按编译的说法，终结符，而上文的S,E,T,op,num等都是非终结符）应该如何处理。简单的说，上文的算法是一个非终结符一个函数；而现在需要一个终结符对应一个函数，顺序读到某终结符时就调用一次对应的函数。该函数将根据当前栈中的状况做合适的处理(压栈/出栈等)，并返回“匹配/不匹配/错误”。在任何一步中返回“错误”（表示无论后续时什么都不可能正确了。如在没有 '( '的情况下出现了 ') '之类的）则提前终止，结果为“不匹配”；否则继续到结束，以最后一次的返回为最终结果。