【手搓一个脚本语言】六、用C语言抽象语法树AST计算表达式的值

devtools/2025/2/22 4:23:40/

【手搓一个脚本语言】六、用C语言抽象语法树AST计算表达式的值

  • 接上一篇【手搓一个脚本语言】五、用C语言抽象语法树AST解析简单的表达式字符串（括号）-CSDN博客代码，再进一步改进！！！
  • 目标：用抽象语法树AST解析完表达式后，计算表达式，求出表达式的正解结果！

1、表达式的计算方法

  • 中缀表达式，可读性程度最高，人脑计算起来方便，编程实现比较复杂！
  • 前缀表达式，可读性程度中等，对应LISP语言的表达式，编程实现容易！
  • 后缀表达式，可读性程度最差，但编程实现轻松！！！
  • 这里采用最容易编程实现的计算后缀表达式的方法！！！

2、统计AST的节点数

  • 为计算表达式做准备！
/* count all astnode */
static void
astnode_count_all (AstNode node, int *cnt)
{if (node != NULL){astnode_count_all (node->left, cnt);astnode_count_all (node->right, cnt);if (node->token.type == T_SUBA)astnode_count_all (node->token.V.aobj, cnt);else(*cnt)++;}
}/* count astnode */
int
astnode_count (AstNode node)
{int count = 0;astnode_count_all (node, &count);return count;
}

3、用后序遍历的方式将AST中的所有值保存到数组中去，形成一个后缀表达式

  • 在外部定义一个数组，长度为上一步统计的AST的节点数，将数组指针和数组的索引地址传给函数
/* postorder traverse ast save to array */
void
astnode_postorder_trav_toa (AstNode node, Token tks[], int *idx)
{if (node != NULL){astnode_postorder_trav_toa (node->left, tks, idx);astnode_postorder_trav_toa (node->right, tks, idx);switch (node->token.type){case T_OPER: tks[*idx] = node->token; (*idx)++; break;case T_NUMB: tks[*idx] = node->token; (*idx)++; break;case T_SUBA: astnode_postorder_trav_toa (node->token.V.aobj, tks, idx);  break;}}
}

4、计算表达式函数

  • 上一步完成，循环读出后缀表达式数组中的Token，如果是数字，压入栈，如果是运算符，则根据运算符计算出结果，再将结果压入栈，循环结束，栈底的值即为结果！！！
/* evaluate astnode */
Token
eval_astnode (AstNode node)
{int index = 0, count = 0;Token *tks, tk, stk[16] = {0};int sp = 0;count = astnode_count (node);tks = (Token*) malloc (count * sizeof(Token));astnode_postorder_trav_toa (node, tks, &index);PF("Node count: %d\n", count);PF("Node index: %d\n", index);for (int i = 0; i < count; i++){switch (tks[i].type){case T_NUMB:{PFI("PUSH %ld, SP: %d\n", tks[i].V.ival, sp);stk[sp] = tks[i]; sp = sp + 1;}break;case T_OPER:{switch (tks[i].V.oval[0]){case '+':PFI("ADD %ld %ld", stk[sp-2].V.ival, stk[sp-1].V.ival);stk[sp-2].V.ival = stk[sp-2].V.ival + stk[sp-1].V.ival;PFI(" ==> %ld\n", stk[sp-2].V.ival);stk[sp-1].type = 0; stk[sp-1].V.nval = 0; sp = sp - 1;break;case '-':PFI("SUB %ld %ld", stk[sp-2].V.ival, stk[sp-1].V.ival);stk[sp-2].V.ival = stk[sp-2].V.ival - stk[sp-1].V.ival;PFI(" ==> %ld\n", stk[sp-2].V.ival);stk[sp-1].type = 0; stk[sp-1].V.nval = 0; sp = sp - 1;break;case '*':PFI("MUL %ld %ld", stk[sp-2].V.ival, stk[sp-1].V.ival);stk[sp-2].V.ival = stk[sp-2].V.ival * stk[sp-1].V.ival;PFI(" ==> %ld\n", stk[sp-2].V.ival);stk[sp-1].type = 0; stk[sp-1].V.nval = 0; sp = sp - 1;break;case '/':PFI("DIV %ld %ld", stk[sp-2].V.ival, stk[sp-1].V.ival);stk[sp-2].V.ival = stk[sp-2].V.ival / stk[sp-1].V.ival;PFI(" ==> %ld\n", stk[sp-2].V.ival);stk[sp-1].type = 0; stk[sp-1].V.nval = 0; sp = sp - 1;break;}}break;}}free (tks);tk = stk[0];return tk;
}

5、测试函数

/* test eval astnode function */
void
test_eval (void)
{AstNode root = NULL;Token tk;//char *st = "1+2*3";//char *st = "1+2*3+4";//char *st = "1*2+3*4";//char *st = "1*2*3+5*6*7";char *st = "(10+20)*30";PF("EXPR: %s\n", st);PF("--------------------\n");root = parse_string (st);PF("--------------------\n");PF(" MID: "); astnode_inorder_trav (root); PF("\n");PF("--------------------\n");PF("PREV: "); astnode_prevorder_trav (root); PF("\n");PF("--------------------\n");astnode_visual_trav (root);PF("--------------------\n");PF("POST: "); astnode_postorder_trav (root); PF("\n");PF("--------------------\n");tk = eval_astnode (root);PF("--------------------\n");PF("RESULT: %ld\n", tk.V.ival);PF("--------------------\n");astnode_free (root);
}

6、编译运行，结果如预期！！！

EXPR: (10+20)*30
--------------------
LPAR: (
NUMB: 10OP: +
NUMB: 20
RPAR: )OP: *
NUMB: 30
--------------------MID:  ( 10 + 20 ) * 30
--------------------
PREV:  ( * ( + 10 20 ) 30 )
--------------------<<[10][+]>[20]
[*]>[30]
--------------------
POST:  10 20 + 30 *
--------------------
Node count: 5
Node index: 5
PUSH 10, SP: 0
PUSH 20, SP: 1
ADD 10 20 ==> 30
PUSH 30, SP: 1
MUL 30 30 ==> 900
--------------------
RESULT: 900
--------------------

7、检查内存分配情况，无误！！！

==3080== Memcheck, a memory error detector
==3080== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3080== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3080== Command: ./gt
==3080== 
EXPR: (10+20)*30
--------------------
LPAR: (
NUMB: 10OP: +
NUMB: 20
RPAR: )OP: *
NUMB: 30
--------------------MID:  ( 10 + 20 ) * 30
--------------------
PREV:  ( * ( + 10 20 ) 30 )
--------------------<<[10][+]>[20]
[*]>[30]
--------------------
POST:  10 20 + 30 *
--------------------
Node count: 5
Node index: 5
PUSH 10, SP: 0
PUSH 20, SP: 1
ADD 10 20 ==> 30
PUSH 30, SP: 1
MUL 30 30 ==> 900
--------------------
RESULT: 900
--------------------
==3080== 
==3080== HEAP SUMMARY:
==3080==     in use at exit: 0 bytes in 0 blocks
==3080==   total heap usage: 7 allocs, 7 frees, 272 bytes allocated
==3080== 
==3080== All heap blocks were freed -- no leaks are possible
==3080== 
==3080== For counts of detected and suppressed errors, rerun with: -v
==3080== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

8、完整代码

/* filename gt.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>/* compile: gcc gt.c -o gt */
/*     run: ./gt           */
/* memcheck: valgrind --leak-check=yes ./gt *//* debug on|off */
#define GT_DEBUG 1
#if GT_DEBUG
#define PFI(...) fprintf (stderr, __VA_ARGS__)
#else
#define PFI(...)
#endif
#define PF(...) fprintf (stderr, __VA_ARGS__)/* define token type */
#define T_OPER  0x21
#define T_NUMB  0x22
#define T_SUBA  0x23/* define astnode datatype */
typedef struct _AstNode *AstNode;/* define token datatype */
typedef struct _Token Token;
struct _Token {union {void *nval;    //nullchar  oval[8]; //operatorlong  ival;    //integerAstNode  aobj;    //sub astnode} V;char type;       //value typechar fill[7];    //unused
};/* define astnode data struct */
struct _AstNode {Token token;AstNode left, right;
};/* create a new astnode */
AstNode
astnode_new (Token tk)
{AstNode node = (AstNode) malloc (sizeof(struct _AstNode));node->token = tk; node->left = NULL; node->right = NULL;return node;
}/* free the astnode */
void
astnode_free (AstNode node)
{if (node != NULL){astnode_free (node->left);astnode_free (node->right);if (node->token.type == T_SUBA)astnode_free (node->token.V.aobj);free (node);}
}/* count all astnode */
static void
astnode_count_all (AstNode node, int *cnt)
{if (node != NULL){astnode_count_all (node->left, cnt);astnode_count_all (node->right, cnt);if (node->token.type == T_SUBA)astnode_count_all (node->token.V.aobj, cnt);else(*cnt)++;}
}/* count astnode */
int
astnode_count (AstNode node)
{int count = 0;astnode_count_all (node, &count);return count;
}/* visual traverse, by level, by left or right */
static void
astnode_visual_trav_lv (AstNode node, int lv, char lr)
{if (node != NULL){astnode_visual_trav_lv (node->left, lv+1, 'L');for (int i = 0; i < lv; i++) PFI("    ");if (lr == 'L') PFI("<");if (lr == 'R') PFI(">");switch (node->token.type){case T_OPER: PFI("[%s]\n",  node->token.V.oval); break;case T_NUMB: PFI("[%ld]\n", node->token.V.ival); break;case T_SUBA: PFI("\n"); astnode_visual_trav_lv (node->token.V.aobj, lv, 'N'); break;}astnode_visual_trav_lv (node->right, lv+1, 'R');}
}/* visual traverse, looks like a tree */
void
astnode_visual_trav (AstNode node)
{astnode_visual_trav_lv (node, 0, 'N');
}/* prevorder traverse ast */
void
astnode_prevorder_trav (AstNode node)
{if (node != NULL){if (node->token.type == T_OPER) PFI(" (");switch (node->token.type){case T_OPER: PFI( " %s", node->token.V.oval); break;case T_NUMB: PFI(" %ld", node->token.V.ival); break;case T_SUBA: astnode_prevorder_trav (node->token.V.aobj); break;}astnode_prevorder_trav (node->left);astnode_prevorder_trav (node->right);if (node->token.type == T_OPER) PFI(" )");}
}/* inorder traverse ast */
void
astnode_inorder_trav (AstNode node)
{if (node != NULL){astnode_inorder_trav (node->left);switch (node->token.type){case T_OPER: PFI( " %s", node->token.V.oval); break;case T_NUMB: PFI(" %ld", node->token.V.ival); break;case T_SUBA: PFI(" ("); astnode_inorder_trav (node->token.V.aobj); PFI(" )"); break;}astnode_inorder_trav (node->right);}
}/* postorder traverse ast */
void
astnode_postorder_trav (AstNode node)
{if (node != NULL){astnode_postorder_trav (node->left);astnode_postorder_trav (node->right);switch (node->token.type){case T_OPER: PFI( " %s", node->token.V.oval); break;case T_NUMB: PFI(" %ld", node->token.V.ival); break;case T_SUBA: astnode_postorder_trav (node->token.V.aobj); break;}}
}/* postorder traverse ast save to array */
void
astnode_postorder_trav_toa (AstNode node, Token tks[], int *idx)
{if (node != NULL){astnode_postorder_trav_toa (node->left, tks, idx);astnode_postorder_trav_toa (node->right, tks, idx);switch (node->token.type){case T_OPER: tks[*idx] = node->token; (*idx)++; break;case T_NUMB: tks[*idx] = node->token; (*idx)++; break;case T_SUBA: astnode_postorder_trav_toa (node->token.V.aobj, tks, idx);  break;}}
}/* get operator priority */
static int
get_priority (char *op)
{if (op[0] == '+') return 1;if (op[0] == '-') return 1;if (op[0] == '*') return 2;if (op[0] == '/') return 2;
}/* define stack height */
#define STCKSIZE 16/* define number buffer length */
#define NUMBSIZE 20/* parse expression string to ast */
AstNode
parse_string (char *estr)
{AstNode head = NULL;AstNode st[STCKSIZE] = {0};AstNode tp[STCKSIZE] = {0};int lv = 0;char nbuf[NUMBSIZE] = {0};int ndx = 0;int idx = 0;char c;c = estr[idx];while (c != '\0'){switch (c){case '0'...'9': //number{char n = estr[idx + 1]; //next charnbuf[ndx] = c; ndx++;if (!(n >= '0' && n <= '9')) //not a number{long  lt = strtol (nbuf, NULL, 10);Token tk = { .type = T_NUMB, .V.ival = lt };AstNode node = astnode_new (tk);if (st[lv] == NULL){if (tp[lv] == NULL) tp[lv] = node;elsePFI("Info: At index %d, Maybe Syntax error!\n", idx);}else{AstNode tmp = st[lv]->right;if (tmp == NULL){st[lv]->right = node;}else{while (tmp->right != NULL)tmp = tmp->right;tmp->right = node;}}PFI("NUMB: %s\n", nbuf);memset (nbuf, 0, NUMBSIZE); ndx = 0; //init nbuf}}break;case '+': case '-': case '*': case '/': //operator{Token tk = { .type = T_OPER, .V.oval[0] = c };AstNode node = astnode_new (tk);int opr = get_priority (tk.V.oval);if (st[lv] == NULL){if (tp[lv] == NULL){st[lv] = node;}else{node->left = tp[lv];st[lv] = node;}}else{int ppr = get_priority (st[lv]->token.V.oval);if (opr > ppr){node->left = st[lv]->right;st[lv]->right = node;}else{node->left = st[lv];st[lv] = node;}}PFI("  OP: %c\n", c);}break;case '(': //left parentheses{lv++; PFI("LPAR: %c\n", c);}break;case ')': //right parentheses{AstNode node = NULL;Token tk = { .type = T_SUBA, .V.aobj = st[lv] };node = astnode_new (tk);if (st[lv-1] == NULL){st[lv-1] = node; st[lv] = NULL; tp[lv] = NULL;}else{if (st[lv-1]->right == NULL){st[lv-1]->right = node;}else{AstNode tmp = st[lv-1]->right;while (tmp->right != NULL)tmp = tmp->right;tmp->right = node;}st[lv] = NULL; tp[lv] = NULL;}lv--; PFI("RPAR: %c\n", c);}break;case ' ': break; //space do nothingdefault:PFI("Error: At index %d, [%c], Syntax error!\n", idx, c); exit (0);}idx++; c = estr[idx];}head = st[lv];return head;
}/* evaluate astnode */
Token
eval_astnode (AstNode node)
{int index = 0, count = 0;Token *tks, tk, stk[16] = {0};int sp = 0;count = astnode_count (node);tks = (Token*) malloc (count * sizeof(Token));astnode_postorder_trav_toa (node, tks, &index);PF("Node count: %d\n", count);PF("Node index: %d\n", index);for (int i = 0; i < count; i++){switch (tks[i].type){case T_NUMB:{PFI("PUSH %ld, SP: %d\n", tks[i].V.ival, sp);stk[sp] = tks[i]; sp = sp + 1;}break;case T_OPER:{switch (tks[i].V.oval[0]){case '+':PFI("ADD %ld %ld", stk[sp-2].V.ival, stk[sp-1].V.ival);stk[sp-2].V.ival = stk[sp-2].V.ival + stk[sp-1].V.ival;PFI(" ==> %ld\n", stk[sp-2].V.ival);stk[sp-1].type = 0; stk[sp-1].V.nval = 0; sp = sp - 1;break;case '-':PFI("SUB %ld %ld", stk[sp-2].V.ival, stk[sp-1].V.ival);stk[sp-2].V.ival = stk[sp-2].V.ival - stk[sp-1].V.ival;PFI(" ==> %ld\n", stk[sp-2].V.ival);stk[sp-1].type = 0; stk[sp-1].V.nval = 0; sp = sp - 1;break;case '*':PFI("MUL %ld %ld", stk[sp-2].V.ival, stk[sp-1].V.ival);stk[sp-2].V.ival = stk[sp-2].V.ival * stk[sp-1].V.ival;PFI(" ==> %ld\n", stk[sp-2].V.ival);stk[sp-1].type = 0; stk[sp-1].V.nval = 0; sp = sp - 1;break;case '/':PFI("DIV %ld %ld", stk[sp-2].V.ival, stk[sp-1].V.ival);stk[sp-2].V.ival = stk[sp-2].V.ival / stk[sp-1].V.ival;PFI(" ==> %ld\n", stk[sp-2].V.ival);stk[sp-1].type = 0; stk[sp-1].V.nval = 0; sp = sp - 1;break;}}break;}}free (tks);tk = stk[0];return tk;
}/**************************************************//* test eval astnode function */
void
test_eval (void)
{AstNode root = NULL;Token tk;//char *st = "1+2*3";//char *st = "1+2*3+4";//char *st = "1*2+3*4";//char *st = "1*2*3+5*6*7";char *st = "(10+20)*30";PF("EXPR: %s\n", st);PF("--------------------\n");root = parse_string (st);PF("--------------------\n");PF(" MID: "); astnode_inorder_trav (root); PF("\n");PF("--------------------\n");PF("PREV: "); astnode_prevorder_trav (root); PF("\n");PF("--------------------\n");astnode_visual_trav (root);PF("--------------------\n");PF("POST: "); astnode_postorder_trav (root); PF("\n");PF("--------------------\n");tk = eval_astnode (root);PF("--------------------\n");PF("RESULT: %ld\n", tk.V.ival);PF("--------------------\n");astnode_free (root);
}/* test parse string function */
void
test_parse (void)
{AstNode root = NULL;//char *st = "1+2-3";//char *st = "1+2-3+4";//char *st = "1+2-3+4-5";//char *st = "100-200+300+400-500";//char *st = "1+2*3";//char *st = "1*2+3";//char *st = "1+2*3+4";//char *st = "1+2+3*4+5+6";//char *st = "1*2+3*4";//char *st = "1*2*3+4*5*6+7*8*9";//char *st = "1*(2+3)";//char *st = "(1+2)*3";//char *st = "1*(2+3+4)*5";//char *st = "1+(2-(3+4+5)-6)+7";//char *st = "(((1+2)-3)+4)-5";char *st = "1+(2-(3+(4-5)))";PF("EXPR: %s\n", st);PF("--------------------\n");root = parse_string (st);PF("--------------------\n");PF(" MID: "); astnode_inorder_trav (root); PF("\n");PF("--------------------\n");PF("PREV: "); astnode_prevorder_trav (root); PF("\n");PF("--------------------\n");PF("POST: "); astnode_postorder_trav (root); PF("\n");PF("--------------------\n");astnode_visual_trav (root);PF("--------------------\n");astnode_free (root);
}/* test astnode function */
void
test_astnode (void)
{AstNode root = NULL, tpl = NULL, tpr = NULL;Token tka = { .type = T_NUMB, .V.ival = 1 };Token tkb = { .type = T_NUMB, .V.ival = 2 };Token tkc = { .type = T_OPER, .V.oval[0] = '+' };Token tkd = { .type = T_NUMB, .V.ival = 3 };Token tke = { .type = T_OPER, .V.oval[0] = '-' };tpl  = astnode_new (tka); //1tpr  = astnode_new (tkb); //2root = astnode_new (tkc); //+root->left  = tpl;root->right = tpr;tpl  = root;tpr  = astnode_new (tkd); //3root = astnode_new (tke); //-root->left  = tpl;root->right = tpr;PF(" MID: ");astnode_inorder_trav (root); PF("\n");PF("PREV: ");astnode_prevorder_trav (root); PF("\n");PF("POST: ");astnode_postorder_trav (root); PF("\n");astnode_free (root);
}/* main function */
int
main (int argc, char *argv[])
{//test_astnode ();//test_parse ();test_eval ();return 0;
}
//-----GT-----//

http://www.ppmy.cn/devtools/147405.html

相关文章

redis的高可用

redis的高可用

redis的高可用 一. 主从模式1.1 工作流程 二. 哨兵模式2.1 工作模式2.2 故障切换 三. 集群3.1 hash槽位3.2 集群缺点 一. 主从模式 redis高可用的基础&#xff0c;哨兵模式和集群都是建立在此基础之上。 主从模式和数据库的主从模式是一样的&#xff0c;主负责写入&#xff0c…
阅读更多...
嵌入式入门Day37

嵌入式入门Day37

作业 驱动机械臂 #include <myhead.h>#define IP "192.168.124.16" #define SERPORT 8888int main(int argc, const char *argv[]) {//创建套接字int oldfd socket(AF_INET, SOCK_STREAM, 0);if (oldfd -1){perror("socket");return -1;}//连接服…
阅读更多...
LLaMA：开放和高效的基础语言模型集

LLaMA：开放和高效的基础语言模型集

大家读完觉得有意义记得关注和点赞&#xff01;&#xff01;&#xff01; 目录 摘要 1 引言 1.1 大模型训练&#xff1a;更多参数 vs 更大的数据集 1.2 LLaMA&#xff1a;减少参数&#xff0c;增大数据集 1.3 内容组织 2 方法&#xff08;Approach&#xff09; 2.1 预训…
阅读更多...
arm架构mysql_基于arm架构linux操作系统centos安装mysql5

arm架构mysql_基于arm架构linux操作系统centos安装mysql5

由于鲲鹏的流行趋势&#xff0c;尝试基于arm的mysql安装 网上很多教程缺斤少两&#xff0c;总是差点意思&#xff0c;亲测后总结一下内容 此教程仅适用于mysql5版本&#xff0c;大于mysql5版本不确保正确 下载地址为&#xff1a;https://obs.cn-north-4.myhuaweicloud.com/obs-…
阅读更多...
每日算法一练：剑指offer——贪心算法与找规律

每日算法一练：剑指offer——贪心算法与找规律

1. 买卖芯片的最佳时机 数组 prices 记录了某芯片近期的交易价格&#xff0c;其中 prices[i] 表示的 i 天该芯片的价格。你只能选择 某一天 买入芯片&#xff0c;并选择在 未来的某一个不同的日子 卖出该芯片。请设计一个算法计算并返回你从这笔交易中能获取的最大利润。 如果…
阅读更多...
Go Redis实现排行榜

Go Redis实现排行榜

文章目录 第一章. 前言1.1. 排行榜的应用场景1.2. Redis在排行榜功能中的优势 第二章. 排行榜系统的功能接口设计2.1. 接口设计的重要性2.2. 核心功能接口2.2.1. 排行榜系统总接口2.2.2. 排行榜数据源接口2.2.3. 排行榜打分器接口2.2.4. 排行榜数据存储接口2.2.5. 排行榜重建机…
阅读更多...
手机实时提取SIM卡打电话的信令声音-双卡手机来电如何获取哪一个卡的来电

手机实时提取SIM卡打电话的信令声音-双卡手机来电如何获取哪一个卡的来电

手机实时提取SIM卡打电话的信令声音 --双卡手机来电如何获取哪一个卡的来电 一、前言 前面的篇章《手机实时提取SIM卡打电话的信令声音-智能拨号器的双SIM卡切换方案》中&#xff0c;我们论述了局域网SIP坐席通过手机外呼出去时&#xff0c;手机中主副卡的呼叫调度策略。 但…
阅读更多...
C#：多线程 简单示例

C#：多线程 简单示例

在C#中&#xff0c;多线程编程是一种提高应用程序性能和响应能力的方法。通过使用多线程&#xff0c;你可以同时执行多个任务&#xff0c;从而充分利用现代多核处理器的能力。C#提供了多种方法和工具来管理和操作线程。 以下是一些关键概念和示例代码&#xff0c;帮助你理解如…
阅读更多...
最新文章

Copyright @ 2022~2023