前缀中缀后缀表达式
它们都是对表达式的记法,它们之间的区别在于运算符相对于操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。
将中缀表达式转换为前缀表达式(1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
(2) 从右至左扫描中缀表达式;
(3) 遇到操作数时,将其压入S2;
(4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
(4-1) 如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈;
(4-2) 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入S1;
(4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
(5) 遇到括号时:
(5-1) 如果是右括号“)”,则直接压入S1;
(5-2) 如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃;
(6) 重复步骤(2)至(5),直到表达式的最左边;
(7) 将S1中剩余的运算符依次弹出并压入S2;
(8) 依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。
实现代码:
int priority(char c) if (c == () return 0; else if (c == + || c == -) return 1; else if (c == * || c == /) return 2; else if (c == )) return 3; void in2pre(char *dest, const char *src) stack char num; stack char opt; for (int i = strlen(src) - 1; i = 0; i--) if (src[i] = 0 src[i] = 9) num.push(src[i]); else if (opt.empty() || priority(src[i]) = priority(opt.top())) opt.push(src[i]); else while (!opt.empty() opt.top() != )) num.push(opt.top()); opt.pop(); if (src[i] == () opt.pop(); else opt.push(src[i]); while (!opt.empty()) num.push(opt.top()); opt.pop(); int i = 0; while (!num.empty()) dest[i++] = num.top(); num.pop(); dest[i] = \0; }将中缀表达式转换为后缀表达式
(1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
(2) 从左至右扫描中缀表达式;
(3) 遇到操作数时,将其压入S2;
(4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
(4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
(4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
(4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
(5) 遇到括号时:
(5-1) 如果是左括号“(”,则直接压入S1;
(5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
(6) 重复步骤(2)至(5),直到表达式的最右边;
(7) 将S1中剩余的运算符依次弹出并压入S2;
(8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。
实现代码:
int priority(char c) if (c == + || c == -) return 1; else if (c == * || c == /) return 2; else if (c == () return 3; else if (c == )) return 0; void in2post(char *dest, const char *src) stack char num; stack char opt; for (int i = 0; i strlen(src); i++) if (src[i] = 0 src[i] = 9) num.push(src[i]); //数字直接入栈 else if (opt.empty() || priority(src[i]) priority(opt.top())) //opt为空或者当前元素为左括号或者当前元素优先级高于栈顶元素 opt.push(src[i]); else while (!opt.empty() opt.top() != () num.push(opt.top()); opt.pop(); if (src[i] == )) opt.pop(); //当前元素为右括号,则弹出左括号 else opt.push(src[i]); //当前元素为运算符,则入栈 while (!opt.empty()) num.push(opt.top()); opt.pop(); int len = num.size(); dest[len] = \0; while (!num.empty()) dest[--len] = num.top(); num.pop(); }表达式求值
公用函数:
int compute(int a, char opt, int b) switch (opt) case +: return a + b; case -: return a - b; case *: return a * b; case /: return a / b; }前缀表达式求值
从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。
int prevalue(const char *str) stack int num; int sum; for (int i = strlen(str) - 1; i = 0; i--) if (str[i] = 0 str[i] = 9) num.push(str[i] - 0); else int a = num.top(); num.pop(); int b = num.top(); num.pop(); sum = compute(a, str[i], b); num.push(sum); return num.top(); }后缀表达式求值
左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
int postvalue(const char *str) stack int num; int sum; for (int i = 0; i strlen(str); i++) if (str[i] = 0 str[i] = 9) num.push(str[i] - 0); else int a = num.top(); num.pop(); int b = num.top(); num.pop(); sum = compute(b, str[i], a); num.push(sum); return num.top(); }中缀表达式求值
建立两个栈num和opt分别用于存储操作数和操作符,左至右扫描表达式,只有当前元素的优先级高于栈顶元素的优先级时才入栈,否则弹出操作符以及操作数进行计算,直到栈顶操作符的优先级低于当前元素的优先级,然后将当前操作符入栈(若当前操作符为右括号,则不入栈,同时将对应的左括号出栈),直到所有操作处理完毕。操作数栈中仅剩下一个元素时,该元素的值即为表达式求和结果。
int priority(char c) if (c == + || c == -) return 1; else if (c == * || c == /) return 2; else if (c == () return 3; else if (c == )) return 0; int invalue(const char *str) stack int num; stack char opt; for (int i = 0; i strlen(str); i++) if (str[i] = 0 str[i] = 9) num.push(str[i] - 0); else if (opt.empty() || opt.top() == ( || priority(str[i]) priority(opt.top())) opt.push(str[i]); else while (!opt.empty() priority(opt.top()) priority(str[i])) char c = opt.top(); if (c == () break; opt.pop(); int a = num.top(); num.pop(); int b = num.top(); num.pop(); int sum = compute(b, c, a); num.push(sum); if (str[i] == )) opt.pop(); else opt.push(str[i]); while (!opt.empty()) char c = opt.top(); opt.pop(); int a = num.top(); num.pop(); int b = num.top(); num.pop(); int sum = compute(b, c, a); num.push(sum); return num.top(); }
注:本文中的代码主要用于体现算法思想,为使程序更加简单,操作数的范围都假定为区间[0,9]。
转载:http://blog.csdn.net/foreverling/article/details/47149507
Java数据结构:前缀、中缀、后缀表达式与逆波兰计算器的实现 文章目录 1 前缀表达式 2 中缀表达式 3 后缀表达式 4 逆波兰计算器 4.1 逆波兰计算器简单实现 4.2 中缀表达式转后缀表达式 4.2.1 思路分析 4.2.2 代码实现 4.3 完整的逆波兰表达式计算器实现
相关文章
- 04·Shell编程-条件表达式
- Spring框架:第五章:Spring EL表达式
- 逆波兰表达式计算
- el表达式和jstl_用二叉树来表示一个简单算术表达式
- java lamba表达式_非负简单函数表达式如何理解
- 【说站】python if三元表达式如何使用
- 4.Prometheus监控入门之PromQL表达式语法学习
- 150. 逆波兰表达式求值
- lambda表达式pythonlist_Python学习笔记之lambda表达式用法详解
- ireport表达式判断是否为0_init函数
- springEL表达式_第二强度理论表达式
- 2022-11-05:给定一个逆波兰式,转化成正确的中序表达式。要求只有必要加括号的地方才加括号。
- 【C++修炼之路】29.lambda表达式
- 【Kotlin】object 对象 ( object 关键字 | 对象声明 | 对象表达式 | 伴生对象 )
- 【Python】字符串 ⑥ ( 对表达式进行格式化 )
- Java8 新特性函数式接口,以及和Lambda表达式的关系详解编程语言
- Linux系统下精彩世界:表达式探索之旅(linux表达式)
- js利用与或运算符优先级实现ifelse条件判断表达式