数据结构中的表达式语法问题

来源：百度知道 编辑：UC知道 时间：2024/05/25 12:10:32
从键盘输入一个表达式，判断它是否符合下面的语法规则：
(1) 表达式只能由单字母、运算符和括号构成，不含数字
(2) 运算符仅包括：+、–、*、/、%。
(3) 括号只能是圆括号，不允许有方括号和花括号
(4) 变量与运算符之间、变量与括号之间允许空格，且空格数不限
(5) 以下是表达式的递归式定义，除此之外都不是正确的表达式：
① 仅有一个字母是表达式
② “表达式 运算符 表达式”和“（表达式）”是表达式
如果判断结果是输入的表达式不符合上述规则，则需要指出错误的位置，如有多个错误只需要指出第一个错误所在位置即可。例如：
输入：A
显示：right
输入：(A)
显示：right
输入：A + A * ( b + c )
显示：right
输入：A * + B
显示： error 3
输入：A * ( Ab + A / bc )
显示：error 5
输入： ( + A )
显示： error 2
输入： ( x+A ( / b
显示： error 4
输入：A+b*(a%b
显示： error 9
输入： ) B + A (
显示：error 1

主要判断方法：
1.先扫描一遍字符串，检查是否有非法字符并清除空格；
2.再次扫描字符串，使用前探法进行语法分析；
3.简单的状态变换；
4.使用栈判断左右括号匹配。

#define CHAR_INVALID -1
#define CHAR_SPACE 0
#define CHAR_LETTER 1
#define CHAR_OP 2
#define CHAR_LB 3
#define CHAR_RB 4

int WhatIsChar(char ch) // -1 非法字符; 0 空格; 1 字母; 2 运算符; 3 左括号; 4 右括号

主要函数如下，如果需要源代码请hi我，VC++6.0编译下通过：

bool AnalysisExpression()
{
int i = 0;
char ch;
int status = -1; //-1 内容还未开始, 0 变量中, 1 运算符中
stcontext cont; //入栈上下文数据
msg = "表达式正确!!!";

while(i < inputstr.GetLength())
{
ch = inputstr.GetAt(i);

switch( WhatIsChar(ch) )
{
case CHAR_SPACE://空格

i++;
break;

case CHAR_LETTER://字母变量

status = 0;
if( i < inputstr.GetLength() - 1)
{
if (!(WhatIsChar(inputstr.GetAt(i + 1)) == CHAR_OP ||
WhatIsC