不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 415|回复: 0

[c/c++] [C数据结构]链式栈(复用链表)

[复制链接]
j2cat 发表于 2018-1-6 19:38:53 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 j2cat 于 2018-1-6 19:43 编辑

LinkStack.h
  1. #ifndef _LINKSTACK_H_
  2. #define _LINKSTACK_H_

  3. typedef void LinkStack;

  4. LinkStack* LinkStack_Create();
  5. void LinkStack_Destroy(LinkStack* stack);
  6. void LinkStack_Clear(LinkStack* stack);
  7. int LinkStack_Push(LinkStack* stack, void* item);
  8. void* LinkStack_Pop(LinkStack* stack);
  9. void* LinkStack_Top(LinkStack* stack);
  10. int LinkStack_Size(LinkStack* stack);

  11. #endif
复制代码
LinkStack.c
  1. #include "LinkStack.h"
  2. #include "linklist.h"
  3. #include <malloc.h>

  4. typedef struct _tag_LinkStackNode {
  5.         TLinkListNode header;
  6.         void* item;
  7. }TLinkStackNode;

  8. LinkStack* LinkStack_Create() {
  9.         return linklist_create();
  10. }
  11. void LinkStack_Destroy(LinkStack* stack) {
  12.         LinkStack_Clear(stack);
  13.         linklist_destroy((LinkList*)stack);
  14. }
  15. void LinkStack_Clear(LinkStack* stack) {
  16.         while (LinkStack_Size(stack) > 0) {
  17.                 LinkStack_Pop(stack);
  18.         }
  19. }
  20. int LinkStack_Push(LinkStack* stack, void* item) {
  21.         TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode));
  22.         int ret = (NULL != node) && (NULL != item);
  23.         if (ret) {
  24.                 node->item = item;
  25.                 ret = linklist_insert((LinkList*)stack, (TLinkListNode*)node, 0);
  26.         }
  27.         if (!ret) {
  28.                 free(node);
  29.         }
  30.         return ret;
  31. }
  32. void* LinkStack_Pop(LinkStack* stack) {
  33.         TLinkStackNode* node = (TLinkStackNode*)linklist_delete((LinkList*)stack, 0);
  34.         void* ret = NULL;
  35.         if (NULL != node) {
  36.                 ret = node->item;
  37.                 free(node);
  38.         }

  39.         return ret;
  40. }
  41. void* LinkStack_Top(LinkStack* stack) {
  42.         TLinkStackNode* node = (TLinkStackNode*)linklist_get(stack, 0);
  43.         void* ret = NULL;
  44.         if (NULL != node) {
  45.                 ret = node->item;
  46.         }
  47.         return ret;
  48. }
  49. int LinkStack_Size(LinkStack* stack) {
  50.         return linklist_length((LinkList*)stack);
  51. }
复制代码

main.c
  1. #include <stdio.h>
  2. #include "LinkStack.h"

  3. int match(char left, char right) {
  4.         int ret = 0;
  5.         switch (left) {
  6.         case '<':
  7.                 ret = (right == '>');
  8.                 break;
  9.         case '[':
  10.                 ret = (right == ']');
  11.                 break;
  12.         case '(':
  13.                 ret = (right == ')');
  14.                 break;
  15.         case '{':
  16.                 ret = (right == '}');
  17.                 break;
  18.         case '\'':
  19.                 ret = (right == '\'');
  20.                 break;
  21.         case '"':
  22.                 ret = (right == '"');
  23.                 break;
  24.         default:
  25.                 ret = 0;
  26.                 break;
  27.         }
  28.         return ret;
  29. }

  30. int isLeft(char c) {
  31.         int ret = 0;

  32.         switch (c) {
  33.                 case '<':
  34.                 case '[':
  35.                 case '(':
  36.                 case '{':
  37.                 case '\'':
  38.                 case '"':
  39.                         ret = 1;
  40.                         break;
  41.                 default:
  42.                         ret = 0;
  43.                         break;
  44.         }

  45.         return ret;
  46. }

  47. int isRight(char c) {
  48.         int ret = 0;

  49.         switch (c) {
  50.         case '>':
  51.         case ']':
  52.         case ')':
  53.         case '}':
  54.         case '\'':
  55.         case '"':
  56.                 ret = 1;
  57.                 break;
  58.         default:
  59.                 ret = 0;
  60.                 break;
  61.         }

  62.         return ret;
  63. }

  64. int scanner(const char* code) {
  65.         LinkStack* stack = LinkStack_Create();
  66.         int i = 0;
  67.         int ret = 0;
  68.         while ('\0' != code[i]) {
  69.                 if (isLeft(code[i])) {
  70.                         LinkStack_Push(stack, (void*)(code + i));
  71.                 }
  72.                
  73.                 if (isRight(code[i])) {
  74.                         char* c = (void*)LinkStack_Pop(stack);
  75.                         if (NULL == c || !match(*c, code[i])) {
  76.                                 printf(""%c" does not match!\n", code[i]);
  77.                                 ret = 0;
  78.                                 break;
  79.                         }
  80.                 }
  81.                 i++;
  82.         }
  83.         if (LinkStack_Size(stack) == 0 && code[i] == '\0') {
  84.                 printf("succeed!\n");
  85.                 ret = 1;
  86.         }
  87.         else {
  88.                 printf("Invalid code!\n");
  89.                 ret = 0;
  90.         }
  91.         LinkStack_Destroy(stack);
  92.         return ret;
  93. }



  94. int main(void) {

  95.         const char* str = "#include <stdio.h>int main(void){int arr[4][5];int (*p)]; p = arr; return 0;}";
  96.         scanner(str);
  97.         getchar();
  98.         return 0;
  99. }
复制代码
main2.c
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include "LinkStack.h"

  4. int isNumber(char ch) {
  5.         return (ch >= '0') && (ch <= '9');
  6. }

  7. int isOperator(char ch) {
  8.         return (ch == '+') || (ch == '-') || (ch == '*') || (ch == '/');
  9. }

  10. int priority(char ch) {
  11.         int ret = 0;
  12.         if (ch == '+' || ch == '-') {
  13.                 ret = 1;
  14.         }
  15.         else if (ch == '*' || ch == '/') {
  16.                 ret = 2;
  17.         }
  18.         return ret;
  19. }

  20. int changed(const char* ch) {
  21.         int ret = *ch - '0';
  22.         return ret;
  23. }

  24. char RightOrLeft(int right, int left, char op) {
  25.         int ret = 0;

  26.         switch (op) {
  27.             case '+':
  28.                         ret = right + left;
  29.                         break;
  30.                 case '-':
  31.                         ret = right - left;
  32.                         break;
  33.                 case '*':
  34.                         ret = right * left;
  35.                         break;
  36.                 case '/':
  37.                         ret = right / left;
  38.                         break;
  39.                 default:
  40.                         printf("error!\n");
  41.                         break;
  42.         }

  43.         return ret;
  44. }

  45. int compute(const char* exp) {
  46.         LinkStack* stack = LinkStack_Create();
  47.         int iexp[50] = { 0 };
  48.         int i = 0;
  49.         int j = 0;
  50.         int ret = 0x7FFFFFFF;
  51.         while ('\0' != exp[i]) {
  52.                 if (isNumber(exp[i])) {
  53.                         iexp[j] = changed(&exp[i]);
  54.                         LinkStack_Push(stack, (void*)&iexp[j]);
  55.                         j++;
  56.                 }
  57.                 else if (isOperator(exp[i]) && 1 < LinkStack_Size(stack)) {
  58.                         iexp[j] = RightOrLeft(*(int*)LinkStack_Pop(stack), *(int*)LinkStack_Pop(stack), exp[i]);
  59.                         LinkStack_Push(stack, (void*)&iexp[j]);
  60.                         j++;
  61.                 }
  62.                 else {
  63.                         printf("Invalid expression!");
  64.                         break;
  65.                 }
  66.                 i++;
  67.         }
  68.         if ((LinkStack_Size(stack) == 1) && (exp[i] == '\0')) {
  69.                 ret = *(int*)LinkStack_Pop(stack);
  70.         }
  71.         else {
  72.                 printf("Invalid expression!");
  73.         }

  74.         LinkStack_Destroy(stack);

  75.         return ret;
  76. }

  77. int main(void) {
  78.         printf("9 + (3 - 1) * 5 + 8 / 2 = %d\n", compute("931-5*+82/+"));
  79.         getchar();
  80.         return 0;
  81. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|不学网

GMT+8, 2018-9-19 04:57

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表