进制转换
关于进制转化问题，可以利用栈的先进后出选择很方便的实现，以二进制为例，将一个十进制数8转化为二进制的，实现思路如下图所示：
整个递归过程就是将要转化的10进制数不断除以2，将余数保存起来，当要转换的数据为0时，递归终止。将所有余数逆序输出，就是转换完的数，根据这一特性，可以将所有余数顺序入栈，逆序出栈。实现代码如下所示：
void convert(Stack<char>& s, int n, int base)
{
char digit[] = { '0' ,'1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
if (0 < n)
{
convert(s, n / base, base);
s.push(digit[n % base]);
}
}
括号匹配
利用栈的先进后出规则，可以很方便的实现括号匹配。利用栈实现括号匹配的总体实现思路是先将所有的左括号入栈，然后再依次弹出，判断弹出的元素与入栈的元素是否相等，如果相等，则匹配，否则不匹配，最后，经过一次循环，如果栈中还有元素，说明整个表达式的括号不匹配。具体的实现思路，如下图所示：
根据以上思路，实现代码如下所示：
/*
//判断是否匹配，每次判断栈是否为空，
若栈已经弹出所有元素，则直接返回false
*/
bool brackets_match(const char exp[], int lo, int hi)
{
Stack<char> S;
for (int i = lo; i <=hi; i++)
{
switch (exp[i]) //左括号入栈
{
case '(':
case '[':
case '{':
S.push(exp[i]);
break;
case ')':
if ((S.empty()) || (S.pop() != '('))
{
return false;
}
break;
case ']':
if ((S.empty()) || (S.pop() != '['))
{
return false;
}
break;
case '}':
if ((S.empty()) || (S.pop() != '{'))
{
return false;
}
break;
}
}
return S.empty(); //匹配完之后，栈中还包含括号，则说明括号不匹配
}
逆波兰式
传统的表达式中，运算符位于操作数中间，这种表达方式虽然便于人类理解，但是，对于计算机而言，这样的操作非常不便于计算，计算机利用表达式求值时，通常将传统的自然表达方法转化为后缀表达式，这种后缀表达方式称之为逆波兰式，中缀表达式和后缀表达式的转换方式如下所示：
中缀表达式：(1+2)*3+6
后缀表达式：12+3*6+
需要注意的是表示运算顺序的括号在后缀表达式被去掉了，因为后缀表达式本身包含着运算顺序的信息。
综上，根据逆波兰式的特点，利用栈先进后出的特点，可以很方便地实现中缀表达式转换为逆波兰式的步骤如下：
-
定义两个栈是s1,s2，一个用来存放运算符，另一个用来存储操作数和运算符。并默认‘#’是最低优先级的运算符，送入栈S1
-
遍历表达式字符串，对于每一个字符，如果是操作数，直接送入栈s1,如果是运算符，需要做一下判断：
-
将该运算符与栈s1栈顶的运算符做优先级比较，如果该运算符优先级大于栈顶运算符的优先级，将其压入S1栈中。否则，将s1的栈顶元素弹出，送入s2栈中，直至s1的栈顶运算符低于该运算符的优先级，最后将该运算符压入栈上s1中
-
如果遇到括号，如果是‘（’，则直接压入栈中，并且匹配最近的’）‘，并将括号之间的运算符全部从栈s1中弹出，压入栈s2中，最后，再将栈顶元素’（‘舍弃。
遍历整个字符串，重复执行2，3，4步。
最后，根据整个运算的步骤，用C++的实现代码如下所示：
#pragma once
/*
*
* 逆波兰表达式，后缀表达式
* 中缀表达式： （1+2）*3+4
* 后缀表达式： 12+3*4+
* 用栈实现： 步骤：1>定义两个栈，S1和S2，S1用来保存运算符，S2用来保存处理操作
*
*
*/
//定义两个全局变量，用来接收返回的字符串
int length=0; //记录字符串长度，便于输出
char returnStr[256]; //记录字符串
void RPN(char* express)
{
Stack<char> s1;
Stack<char> s2;
//返回的内容
char* p = express;
char c; //临时变量，用于记录栈中弹出的元素
//length = 0;
s1.push('#'); //默认#是最低优先级的运算符
while (*p != '\0')
{
if(*p=='(') //遇到（直接存入s1栈中
{
s1.push(*p);
}
else if (*p == ')') //遇到）匹配最近的（，并将这些元素全部放入栈s2中
{
while (s1.top() != '(')
{
s2.push(s1.pop());
}
s1.pop(); //记得抛弃入栈的'('符号
}
else if (*p >= '0' && *p <= '9') //操作数全部放入栈S2中
{
s2.push(*p);
}
else if (*p == '+' || *p == '-') //
{
/*
//如果该运算符优先级小于s1栈顶元素，则将s1
的栈顶元素弹出，送入s2栈中,直至s1的栈顶运算符低于该运算符的优先级
*/
if (s1.top() == '*' || s1.top()=='/') //小于s1的栈顶元素
{
//将s1的栈顶元素全部弹出，放入s2中
//直到s1的栈顶运算符小于该运算符
while (s1.top()!='#' )
{
if (s1.top() == '(')
{
break;
}
else
{
s2.push(s1.pop());
}
}
}
s1.push(*p);
}
/*
如果该运算符大于或者等于S1栈顶的运算符优先级，将其
压入s1的栈中
*/
else if (*p == '*' || *p == '/')
{
c = s1.top();
if (c == '(')
{
break;
}
else
{
s1.push(*p);
}
}
p++;
}
while (s1.top()!='#')
{
s2.push(s1.pop());
}
//栈中逆序，字符串中顺序
while (!s2.empty())
{
returnStr[length++] = s2.pop();
}
}
注意：栈s2中的所有元素都是逆序的，为了输出顺序的表达式，还需要将栈s2中的所有的元素逆序处理。
用逆波兰表达式实现表达式计算
将中缀表达式转换为逆波兰式之后，就可以很容易的实现表达式的计算，整个计算过程的步骤，如下所示：
- 定义一个栈s,并且遍历每个字符：
- 当前字符是操作数时直接压入栈s中；
- 当前字符是运算符时，在栈s中弹出需要相应数量的运算符，利用该运算符进行计算，并将该运算后的结果重新压入栈s中。
综上所述：用C++实现的代码如下所示：
float compute(char* exp,int length)
{
float a = 0; //临时变量，用来保存临时计算结果
float b = 0;
Stack<float> s; //定义一个栈用来存储计算结果
length = length - 1;
while (length>=0)
{
if (exp[length] >= '0' && exp[length] <= '9') {
s.push((float)(exp[length]-48));
}
else if (exp[length] == '+')
{
a = (float)s.pop();
b = (float)s.pop();
s.push(a + b);
}
else if (exp[length] == '-')
{
a = (float)s.pop();
b = (float)s.pop();
s.push(a - b);
}
else if (exp[length] == '*')
{
a = (float)s.pop();
b = (float)s.pop();
s.push(a * b);
}
else if (exp[length] == '/')
{
a = (float)s.pop();
b = (float)s.pop();
s.push(a / b);
}
length--;
}
//result = s.top();
return s.top();
}
注意：在代码实现过程中，字符串中的数字是字符型的，需要将其转换为单浮点型数据，根据ASCII码，将每个字符减去48即可。
网友评论