算法题---带加减乘除和括号的单字母变量表达式转化成逆波兰式
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法题---带加减乘除和括号的单字母变量表达式转化成逆波兰式,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3029字,纯文字阅读大概需要5分钟。
内容图文
#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define STACK_INIT_SIZE 100 #define STACK_INCREAMENT 10 #pragma warning(disable:4996)//我用的vs2015,不加这句用scanf会报错(使用了unsafe的函数) typedef struct { //栈char *base; char *top; int stackSize; } Stack; void initStack(Stack &stack) { //初始化栈 stack.base = stack.top = (char *)malloc(sizeof(char) * STACK_INIT_SIZE); stack.stackSize = STACK_INIT_SIZE; } void push(Stack &S, char p) { //入栈if (S.top - S.base >= S.stackSize) { S.base = (char*)realloc(S.base, (S.stackSize + STACK_INCREAMENT)*sizeof(char)); S.top = S.stackSize + S.base; S.stackSize += STACK_INCREAMENT; } *S.top++ = p; } void pop(Stack &stack, char &p) { //出栈if (stack.base == stack.top) { p = NULL; return; } p = *--stack.top; } char getTop(Stack stack) { //获得栈顶元素if (stack.base == stack.top) return NULL; return *(stack.top - 1); } char *NIBOLAN(char *e) /* 返回表达式e的逆波兰式 */ {//栈s1用于存放运算符,栈s2用于存放逆波兰式 Stack s1, s2;initStack(s1);initStack(s2); push(s1, ‘#‘); //假设字符‘#‘是运算级别最低的运算符,并压入栈s1中 //p指针用于遍历传入的字符串,ch用于临时存放字符,length用于计算字符串长度 char *p = e, ch;int length = 0; for (; *p != ‘\0‘; p++)//逐个字符访问 { switch (*p) { //遇‘(‘则直接入栈s1 //遇‘)‘则将距离栈s1栈顶的最近的‘(‘之间的运算符,逐个出栈,依次送入栈s2,此时抛弃‘(‘case‘(‘:push(s1, *p); break; case‘)‘:while (getTop(s1) != ‘(‘) { pop(s1, ch); push(s2, ch); }pop(s1, ch); break; //遇下列运算符,则分情况讨论: //1.若当前栈s1的栈顶元素是‘(‘,则当前运算符直接压入栈s1; //2.否则,将当前运算符与栈s1的栈顶元素比较,若优先级较栈顶元素大,则直接压入栈s1中, // 否则将s1栈顶元素弹出,并压入栈s2中,直到栈顶运算符的优先级别低于当前运算符,然后再将当前运算符压入栈s1中case‘+‘: case‘-‘: for (ch = getTop(s1); ch != ‘#‘; ch = getTop(s1)) { if (ch == ‘(‘) break; else pop(s1, ch); push(s2, ch); }push(s1, *p); length++; break; case‘*‘: case‘/‘: for (ch = getTop(s1); ch != ‘#‘&&ch != ‘+‘&&ch != ‘-‘; ch = getTop(s1)) { if (ch == ‘(‘) break; else pop(s1, ch); push(s2, ch); }push(s1, *p); length++; break; default: push(s2, *p); length++; } } //若栈s1非空,则将栈中元素依次弹出并压入栈s2中while (s1.base!=s1.top && getTop(s1) != ‘#‘) { pop(s1, ch); push(s2, ch); } //最后将栈s2输出,逆序排列成字符串;char *result; result = (char *)malloc(sizeof(char)*(length + 1)); result += length; * result = ‘\0‘; result--; for (; s2.base!=s2.top; result--) { pop(s2, ch); * result = ch; } ++result; return result; } void main() { while (1) { char str[100]; int i; for (i = 0; i<100; i++)str[i]= ‘\0‘; printf("请输入表达式:\n"); scanf("%s",str); printf("%s", NIBOLAN(str)); } }
(1)首先,需要分配2个栈,栈s1用于临时存储运算符(含一个结束符号),此运算符在栈内遵循越往栈顶优先级越高的原则;栈s2用于输入逆波兰式,为方便起见,栈s1需先放入一个优先级最低的运算符,在这里假定为‘#‘;
(2)从中缀式的左端开始逐个读取字符x,逐序进行如下步骤:
1.若x是操作数,则分析出完整的运算数(在这里为方便,用字母代替数字),将x直接压入栈s2;
2.若x是运算符,则分情况讨论:
若x是‘(‘,则直接压入栈s1;
若x是‘)‘,则将距离栈s1栈顶的最近的‘(‘之间的运算符,逐个出栈,依次压入栈s2,此时抛弃‘(‘;
若x是除‘(‘和‘)‘外的运算符,则再分如下情况讨论:
若当前栈s1的栈顶元素为‘(‘,则将x直接压入栈s1;
若当前栈s1的栈顶元素不为‘(‘,则将x与栈s1的栈顶元素比较,若x的优先级大于栈s1栈顶运算符优先级,则将x直接压入栈s1。否者,将栈s1的栈顶运算符弹出,压入栈s2中,直到栈s1的栈顶运算符优先级别低于(不包括等于)x的优先级,或栈s2的栈顶运算符为‘(‘,此时再则将x压入栈s1;
(3)在进行完(2)后,检查栈s1是否为空,若不为空,则将栈中元素依次弹出并压入栈s2中(不包括‘#‘);
(4)完成上述步骤后,栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理,因为此时表达式的首字符位于栈底;
原文:http://www.cnblogs.com/luckyraye/p/6715167.html
内容总结
以上是互联网集市为您收集整理的算法题---带加减乘除和括号的单字母变量表达式转化成逆波兰式全部内容,希望文章能够帮你解决算法题---带加减乘除和括号的单字母变量表达式转化成逆波兰式所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。