后缀表达式
所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符是放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。
如:3*(5–2)+7对应的后缀可以表达式为:3.5.2.-*7.+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。
后缀表达式的一个特点就是方便计算。
我们下面只考虑 加减乘除 四种基本运算,以及表达式中没有 负数 的情况。
问题分析
那么我们如何计算一个后缀表达式呢?
可以借用栈来实现。
此外,后缀表达式也可以用一个二叉树来表示和计算,但是我们这里就不细讲啦!
思路
我们先抛开问题中一些具体的细节(如:是用‘.’作为操作数的结束符号),方便理清对于整个问题的一个思路。
还是用之前那个例子:
3.5.2.-*7.+@
我们从后缀表达式左边开始一边读取数据一边压入栈中,当遇到了运算符时,就将栈中的操作符以及紧邻的两个操作数出栈进行相应的运算,运算结果压入栈中作为新的操作数,然后继续从表达式中读取数据。反复进行以上操作直到得到运算结果。
过程如下图:
一些细节和问题
在了解了一个大概的思路之后,我们就需要考虑程序实现中的一些细节问题了。
一、数据类型处理
一个后缀表达式中有操作数这样的数字,也有运算符这样的符号,所以最终是以博主都用char类型进行存储的。
那么我们如何从以char类型存储了部分表达式的栈中,将操作数和运输符分别读取出来进行运算呢?
需要注意,我们在压入栈中时,是一个字符一个字符的压的,所以在栈中的多位数是倒过来的,如:123压入栈中从栈顶开始看就是321。
下面是从栈中读取出一个操作数的代码段:
//从char型栈中读取出一个int型操作数 int get_num() { int sum(0); for(int i = 1; s.top() != '.'; i *= 10) { sum += (int)(s.top() - '0') * i; s.pop(); if(s.empty()) break; } return sum; }
二、负数
虽然我们前面说了不考虑表达式中有负数的情况,但是在对表达式的计算过程中仍然可能会产生负数,不过这种情况对于博主来说稍稍好处理一点(读取表达式时,负数的负号与减法运算符相同,有歧义)。
博主处理运算过程中负数的方法是,先压入一个字符0作为符号标记,然后将原数的相反数(就是一个非负数了)压入栈中。在出栈时如果数字串的最后一个是0,就将数据取相反数,重新得到原来的负数。
最终代码
#include<iostream> #include<stack> using namespace std; stack<char> s; int get_num(); //从栈中返回一个整型数字 int main(){ char t(0); while(true) { //输入 cin >> t; if(t == '@') { s.pop(); cout << get_num(); break; } s.push(t); //见运算符 if(t == '+' || t == '-' || t == '*' || t == '/') { //出栈运算符 s.pop(); //出栈两个数字为int型 int a(0), b(0); s.pop(); a = get_num(); // cout << "a = " << a << endl; s.pop(); b = get_num(); // cout << "b = " << b << endl; //计算 int result(0); if(t == '+') result = b + a; else if(t == '-') result = b - a; else if(t == '*') result = b * a; else if(t == '/') result = b / a; // cout << "result = " << result << endl; if(result < 0) { s.push('0'); result = -result; // cout << "result = " << result << endl; } //结果转为char型再入栈 stack<char> c; if(result == 0) { s.push('0'); } while(result != 0) { c.push((char)(result % 10 + '0')); result /= 10; } while(!c.empty()) { s.push(c.top()); c.pop(); } s.push('.'); } } } //------------------------------ //从char型栈中读取出一个int型操作数 int get_num() { int sum(0); char t(0); for(int i = 1; s.top() != '.'; i *= 10) { t = s.top(); sum += (int)(s.top() - '0') * i; s.pop(); if(s.empty()) break; } if(t == '0') sum = -sum; return sum; } /* 测试数据 3.5.2.-*7.+@ 10.28.30./*7.-6.+@ 1000.1000./5.-6.*@ */
总结
后缀表达式是一个比较经典的问题。栈的原理其实很简单,就像一个加了限制的数组,只能从同一端进出数据。
但是在用栈解决一些问题时,你会发现它真的好神奇,也许这就是数据结构和算法的魅力吧!