请用C语言实现一个算法,判断数学表达式是否合法,例如: 合法:“123 * ((456 - 3) + 789)”, 非法:“123(* 456 + 789)”。
时间: 2024-03-19 16:44:20 浏览: 19
好的,我可以帮你实现这个算法。基本思路是使用栈来存储符号,遍历表达式的每一个字符,如果是左括号,就将其入栈;如果是右括号,就将栈顶元素出栈并判断是否为左括号,如果不是则表达式非法;如果是运算符,就判断其前面是否为数字或者右括号,如果不是则表达式非法。最后还要判断栈是否为空,如果不为空则表达式非法。
以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
typedef struct Stack {
char data[MAX_LEN];
int top;
} Stack;
void init(Stack *s) {
s->top = -1;
}
void push(Stack *s, char ch) {
if(s->top == MAX_LEN - 1) {
printf("Stack is full!\n");
exit(1);
}
s->data[++s->top] = ch;
}
char pop(Stack *s) {
if(s->top == -1) {
printf("Stack is empty!\n");
exit(1);
}
return s->data[s->top--];
}
char getTop(Stack *s) {
if(s->top == -1) {
printf("Stack is empty!\n");
exit(1);
}
return s->data[s->top];
}
int isDigit(char ch) {
return ch >= '0' && ch <= '9';
}
int isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
int isLeftParenthesis(char ch) {
return ch == '(';
}
int isRightParenthesis(char ch) {
return ch == ')';
}
int isLegal(char *expr) {
Stack s;
init(&s);
int len = strlen(expr);
int i = 0;
while(i < len) {
if(isLeftParenthesis(expr[i])) {
push(&s, expr[i]);
} else if(isRightParenthesis(expr[i])) {
if(getTop(&s) != '(') {
return 0;
}
pop(&s);
} else if(isOperator(expr[i])) {
if(i == 0 || i == len - 1 || !isDigit(expr[i-1]) || (!isDigit(expr[i+1]) && !isLeftParenthesis(expr[i+1]))) {
return 0;
}
} else if(!isDigit(expr[i])) {
return 0;
}
i++;
}
if(s.top != -1) {
return 0;
}
return 1;
}
int main() {
char expr[MAX_LEN];
printf("Please input a mathematical expression: ");
fgets(expr, MAX_LEN, stdin);
if(isLegal(expr)) {
printf("The expression is legal.\n");
} else {
printf("The expression is illegal.\n");
}
return 0;
}
```
这个算法可以处理基本的四则运算和括号嵌套,但是还有很多边界情况需要考虑,比如连续的符号、小数点等等,如果需要更加严谨的实现可以根据实际需求进行修改。