首页 > 代码库 > 栈应用2-无括号后缀表达式
栈应用2-无括号后缀表达式
将算数表达式a+b+c*d转换成后缀表达式ab+cd*+，就可以利用栈来实现这种有优先级的运算，因此首先可以使用栈来将一种表达式转化成对应的后缀表达式。
下面是实现的转换算法，注意不能带括号，支持+-*/运算符，stack的实现我可以去掉了错误检测，因为默认已经声明好了足够大小的栈。
栈头文件stack.h
1 /*数组栈*/ 2 #include "iostream" 3 #include "stdlib.h" 4 5 #define minSize 5 6 #define emptyStack -1 7 #define fullStack -2 8 #define log(s); std::cout<<s<<std::endl; 9 10 typedef struct _stack_11 {12 int capacity;13 int topOfStack;14 char *Array;15 }stack;16 17 stack *createStack(int maxSize)18 {19 stack *s;20 if (maxSize < minSize)21 {22 return nullptr;23 }24 s = (stack *)malloc(sizeof(stack));25 s->Array = (char *)malloc(sizeof(char) * maxSize);26 s->capacity = maxSize;27 s->topOfStack = emptyStack;/*初始化为空栈*/28 return s;29 }30 31 int isEmpty(stack *s)/*是否为空栈*/32 {33 return s->topOfStack == emptyStack;34 }35 36 void push(stack *s, char data)/*压栈*/37 {38 ++s->topOfStack;39 s->Array[s->topOfStack] = data;40 }41 42 void pop(stack *s)/*弹出栈*/43 {44 if (isEmpty(s))45 {46 return;47 }48 --s->topOfStack;49 }50 51 char top(stack *s)/*访问栈顶元素*/52 {53 if (isEmpty(s))54 {55 return emptyStack;56 }57 return s->Array[s->topOfStack];58 }59 60 void makeEmpty(stack *&s)/*置空栈*/61 {62 free(s->Array);63 free(s);64 s = nullptr;65 }
主函数main.cpp
1 #include "stack.h" 2 #include "string" 3 4 int isSymbal(char s) 5 { 6 if (s == ‘+‘ || s == ‘*‘||s==‘-‘||s==‘/‘) 7 { 8 return 1; 9 }10 return 0;11 }12 13 int isBigger(char s1,char s2)//比较是否 s1不比s2 的优先级低14 {15 if (s1 == ‘*‘||s1==‘/‘)//*有最高优先级16 {17 return 1;18 }19 else20 {21 if (s2 == ‘*‘||s2==‘/‘)22 {23 return 0;24 }25 else26 return 1;27 }28 }29 30 int main(void)31 {32 stack *st = createStack(10);33 std::string s;34 std::cin >> s;35 char i;36 for (auto &i:s)37 {38 if (isSymbal(i))39 {40 if (isEmpty(st))//是空栈的时候41 {42 push(st, i);43 }44 else//不是空栈的时候45 {46 if (!isBigger(top(st), i))//栈顶的字符是否比较新读取的字符优先级不小47 {48 push(st,i);49 }50 else51 {52 std::cout << top(st) << " ";53 pop(st);54 push(st, i);55 }56 }57 continue;58 }59 std::cout << i << " ";60 }61 while (!isEmpty(st))62 {63 std::cout << top(st) << " ";64 pop(st);65 }66 std::cout << "" << std::endl;67 system("pause");68 return 0;69 }
我使用的结果是这样：
如有错误，请读者指出，不胜感激。
以上。
栈应用2-无括号后缀表达式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。