栈相关算法
副标题#e#
－括号匹配
int match(char * cs, int size);
1.做一个空栈。读入字符直到文件尾。
2.对读入的字符举办判定，
2.1假如字符是一个左括号，则入栈；
2.2假如字符是一个右括号，假如栈空或弹出的左括号不匹配，则匹配失败；
2.3输入竣事，假如栈非空，则匹配失败，不然匹配乐成。
－计较后缀表达式的值(假定后缀表达式正确)
int postfixValue(char * expression, int size);
1.做一个空栈，读入字符直到文件尾。
2.对读入的字符举办判定，
2.1假如是数字，则入栈；
2.2假如是运算符，则弹出两个数字并将计较功效入栈。
3.计较完毕后，最后弹出的值即为最终计较功效。
－中缀表达式转后缀表达式(假定中缀表达式正确)
void convertExpression(char * expression, int size);
1.做一个空栈，读入字符直到文件尾。
2.对读入的字符举办判定，
2.1假如是操纵数，则直接输出；
2.2假如是运算符(+-*/)
2.2.1假如栈不空，而且栈顶元素的优先级大于当前运算符优先级，则输出栈中所有优先级大于当前元素的运算符；
2.2.2当前元素入栈；
2.2.3上述四个运算符优先级均大于'(‘优先级。
2.3假如是运算符'(‘，则入栈。
2.4假如是运算符’)’，则出栈所有'(‘之前的栈元素，'(‘出栈，但不插手最终表达式。
#p#副标题#e#
3.输入完毕后，输出所有剩下的栈元素。
mystack.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "stackar.h"
#define TRUE 1
#define FALSE 0
static int left(char c);
static int right(char c);
static int pair(char left, char right);
int match(char * cs, int size);
int postfixValue(char * expression, int size);
static int compareSymbol(char symbol, char prevSymbol);
void convertExpression(char * expression, int size);
int main()
{
char chars[] = "1 + {5 * [4 - (4 - 10) + 2 * 23] + 12 / 11}(";
if(match(chars, strlen(chars)))
puts("true");
else
puts("false");
////////////////////////////////////
char exp1[] = "6523+8*+3+*";
printf("postfixValue=%d\n",postfixValue(exp1, strlen(exp1)));
///////////////////////////////////
char exp2[] = "a+b*c+(d*e+f)*g";
convertExpression(exp2, strlen(exp2));
return 0;
}
/* 括号匹配进程 */
int match(char * cs, int size)
{
int i;
int ch;
Stack s = CreateStack(size);
for (i = 0; i < size; i++)
{
ch = *(cs + i);
if (left(ch))
Push(ch, s);
else if (right(ch))
if (IsEmpty(s) || !pair(TopAndPop(s), ch))
return FALSE;
}
if (!IsEmpty(s))
return FALSE;
return TRUE;
}
/* 判定是否为左括号 */
static int left(char c)
{
if (c == '(' || c == '[' || c == '{')
return TRUE;
return FALSE;
}
/* 判定是否为右括号 */
static int right(char c)
{
if (c == ')' || c == ']' || c == '}')
return TRUE;
return FALSE;
}
/* 判定是否配对 */
static int pair(char left, char right)
{
if ((left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}'))
return TRUE;
return FALSE;
}
/* 计较后缀(逆波兰)表达式的值 */
int postfixValue(char * expression, int size)
{
int i;
int ch;
int tmp = 0;
Stack s = CreateStack(size);
for (i = 0; i < size; i++)
{
ch = *(expression + i);
if (isdigit(ch))
Push(ch - '0', s);
else
switch(ch)
{
case '+':
Push(TopAndPop(s) + TopAndPop(s), s);
break;
case '-':
tmp = TopAndPop(s);
Push(tmp - TopAndPop(s), s);
break;
case '*':
Push(TopAndPop(s) * TopAndPop(s), s);
break;
case '/':
tmp = TopAndPop(s);
Push(tmp / TopAndPop(s), s);
break;
default :
fprintf(stderr, "Wrong expression.\n");
exit(1);
}
}
return TopAndPop(s);
}
/* 中缀表达式转后缀表达式 */
void convertExpression(char * expression, int size)
{
int i;
int ch;
Stack s = CreateStack(size);
for (i = 0; i < size; i++)
{
ch = *(expression + i);
if (isalpha(ch))
printf("%c ", ch);
else
{
switch(ch)
{
case '+':
case '-':
case '*':
case '/':
if (!IsEmpty(s) && compareSymbol(ch, Top(s)) <= 0)
{
printf("%c ", TopAndPop(s));
while (!IsEmpty(s) && compareSymbol(ch, Top(s)) <= 0)
printf("%c ", TopAndPop(s));
}
Push(ch, s);
break;
case '(':
Push(ch, s);
break;
case ')':
while (!IsEmpty(s))
{
if (Top(s) != '(')
printf("%c ", TopAndPop(s));
else
{
Pop(s);
break;
}
}
break;
default :
fprintf(stderr, "Wrong expression.\n");
exit(1);
}
}
}
while (!IsEmpty(s))
printf("%c ", TopAndPop(s));
}
/* equal:0; bigger:1; smaller:-1 */
static int compareSymbol(char symbol, char prevSymbol)
{
if (prevSymbol == '(')
return 1;
if (symbol == '+' || symbol == '-')
{
if (prevSymbol == '+' || prevSymbol == '-')
return 0;
else
return -1;
}
else
{
if (prevSymbol == '+' || prevSymbol == '-')
return 1;
else
return 0;
}
}
本文出自 “子 孑” 博客，请务必保存此出处http://zhangjunhd.blog.51cto.com/113473/102014
