C语言实现算符优先分析法进行表达式语法分析与计算

本文提供一个使用C语言实现的算符优先分析法程序，用于分析输入的算术表达式语法是否正确，并在语法正确的情况下计算表达式的值。

代码实现c#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <ctype.h>

typedef struct { char* data; // 存储表达式 int top; // 栈顶指针，初始值为-1表示空栈} SeqStack;

// 构造空栈void InitStack(SeqStack* S, int size) { S->data = (char*)malloc(size * sizeof(char)); S->top = -1;}

// 元素入栈void Push(SeqStack* S, char e) { S->top++; S->data[S->top] = e;}

// 栈出栈，返回出栈元素char Pop(SeqStack* S) { char e = S->data[S->top]; S->top--; return e;}

// 判断运算符的优先级int Priority(char op) { if (op == '+' || op == '-') { return 1; } else if (op == '*' || op == '/') { return 2; } else { return 0; }}

// 执行运算int ExecuteOperation(int num1, int num2, char op) { switch (op) { case '+': return num1 + num2; case '-': return num1 - num2; case '*': return num1 * num2; case '/': return num1 / num2; default: return 0; }}

// 分析语法并计算表达式结果bool AnalyzeExpression(char* expression, int* result) { SeqStack S; int size = sizeof(expression); InitStack(&S, size);

for (int i = 0; expression[i] != '�'; i++) {        if (isdigit(expression[i])) {            int num = 0;            while (isdigit(expression[i])) {                num = num * 10 + (expression[i] - '0');                i++;            }            i--;            Push(&S, num + '0');        } else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/') {            while (S.top != -1 && Priority(S.data[S.top]) >= Priority(expression[i])) {                int num2 = Pop(&S) - '0';                int num1 = Pop(&S) - '0';                char op = Pop(&S);                int result = ExecuteOperation(num1, num2, op);                Push(&S, result + '0');            }            Push(&S, expression[i]);        } else {            return false;  // 非法字符，语法错误        }    }

while (S.top != -1) {        int num2 = Pop(&S) - '0';        int num1 = Pop(&S) - '0';        char op = Pop(&S);        int result = ExecuteOperation(num1, num2, op);        Push(&S, result + '0');    }

*result = Pop(&S) - '0';    return true;}

int main() { char expression[100]; int result;

printf('请输入算术表达式：');    scanf('%s', expression);

if (AnalyzeExpression(expression, &result)) {        printf('计算结果：%d

', result); } else { printf('表达式错误！ '); }

return 0;}

代码说明

1. 数据结构: 使用栈 SeqStack 存储操作数和运算符，方便进行优先级比较和计算。2. 函数: * InitStack: 初始化栈 * Push: 元素入栈 * Pop: 元素出栈 * Priority: 判断运算符优先级 * ExecuteOperation: 执行算术运算 * AnalyzeExpression: 分析表达式语法并计算结果 * main: 主函数，接收输入并输出结果

算法流程

1. 初始化一个空栈。2. 从左到右遍历表达式： * 如果遇到数字，则将其转换为整数并压入栈中。 * 如果遇到运算符，则将栈顶的运算符与其进行优先级比较，如果栈顶运算符优先级更高或相等，则弹出栈顶的运算符和操作数进行计算，并将结果压入栈中。重复此过程，直到栈顶运算符优先级低于当前运算符，然后将当前运算符压入栈中。 * 如果遇到非法字符，则报错。3. 遍历完表达式后，如果栈中还有运算符，则依次弹出运算符和操作数进行计算，直到栈为空。4. 最后栈中剩下的元素即为表达式的计算结果。

示例

输入表达式：1+2*3-4/2

输出结果：计算结果：5

总结

本文介绍了如何使用C语言实现算符优先分析法，对输入的算术表达式进行语法分析和计算。该算法简单易懂，实现方便，是编译原理中一个重要的基础算法。