#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"
/*********************************************************************************
函数名： isLeft
函数功能：判断是否为左符号 是左符号返回1 不是返回0
参数： 要判断的字符 char类型
返回： 成功返回1 失败返回0
*********************************************************************************/
int isLeft(char c)
{
int ret = 0;
switch (c)
{
case ‘<‘:
case ‘(‘:
case ‘[‘:
case ‘{‘:
case ‘\‘‘: // ‘和 “需要转义字符 原因分别在于字符和字符串 两种情况
case ‘\"‘:
ret = 1;
break;
default :
ret = 0;
break;
}
return ret;
}
/*********************************************************************************
函数名： isRight
函数功能：判断是否为右符号 是右符号返回1 不是返回0
参数： 要判断的字符 char类型
返回： 成功返回1 失败返回0
*********************************************************************************/
int isRight(char c)
{
int ret = 0;
switch (c)
{
case ‘>‘:
case ‘)‘:
case ‘]‘:
case ‘}‘:
case ‘\‘‘: // ‘和 “需要转义字符 原因分别在于字符和字符串 两种情况
case ‘\"‘:
ret = 1;
break;
default :
ret = 0;
break;
}
return ret;
}
/*********************************************************************************
函数名：match
函数功能：判断左右符号是否匹配
函数参数： char left为从栈顶获取的左符号 char right为刚刚获得右符号
返回值：匹配成功返回1 失败返回0
*********************************************************************************/
int match(char left ,char right)
{
int ret = 0;
switch (left)
{
case ‘<‘ :
ret = (right == ‘>‘);
break;
case ‘{‘ :
ret = (right == ‘}‘);
break;
case ‘[‘ :
ret = (right == ‘]‘);
break;
case ‘\‘‘ :
ret = (right == ‘\‘‘);
break;
case ‘\"‘ :
ret = (right == ‘\"‘);
break;
default :
ret = 0;
break;
}
}
/*********************************************************************************
函数名：check
函数功能：检查字符串语法是否匹配
函数参数：想要检查的字符串头地址
返回值：匹配返回1 不匹配返回0
*********************************************************************************/
int check(const char* code)
{
int ret = 1;
char* temp = NULL;
LinkStack* stack = NULL;
stack = Creat_LinkStack();
while(*code != ‘\0‘)
{
if( isLeft(*code) )
{
LinkStack_Push(stack ,(void*)code);
}
if( isRight(*code) )
{
temp = (char*)LinkStack_Pop(stack);
if( (NULL == temp)||(!match(*temp, *code)) )//判断左符号和右符号如果不匹配
{
printf("%c is not match!\n",*code);
ret = 0; //返回失败标准
break;
}
}
code++;
}
if( (0 == Get_LinkStack_Length(stack))&&(‘\0‘ == *code) )
{
printf("Succeed!\n");
ret = 1;
}
else
{
printf("Invalid code!\n");
ret = 0;
}
Destroy_LinkStack(stack);
return ret;
}
int main(int argc, char *argv[])
{
const char* code = "#include <stdio.h>void main(){int TestArr ay[5][5] = { {11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}, {26,27,28,29,30},{31,32,33,34,35}};int* p1 = (int*)(&TestArray + 1); int* p2 = (int*)(*(TestArray + 1) + 6); // *(&t[0] + 1) &t[1] [0]+6+4 printf("", *(*TestArray), *(*(TestArray + 1)), *(*(TestArray + 3) + 3), p1[-8], p2[4]);}";
check(code);
return 0;
}
注意：当需要检测成对出现但又互不相邻的事物时，可以使用栈"后进先出"的特性！栈非常适合于需要"就近匹配"的场合！
#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"
int isNumber(char c)
{
return (‘0‘ <= c) && (c <= ‘9‘);
}
int isOperator(char c)
{
return (c == ‘+‘) || (c == ‘-‘) || (c == ‘*‘) || (c == ‘/‘);
}
int isLeft(char c)
{
return (c == ‘(‘);
}
int isRight(char c)
{
return (c == ‘)‘);
}
int priority(char c)
{
int ret = 0;
if( (c == ‘+‘) || (c == ‘-‘) )
{
ret = 1;
}
if( (c == ‘*‘) || (c == ‘/‘) )
{
ret = 2;
}
return ret;
}
/********************************************************************************************
函数名： transform
函数功能： 将中缀表达式转换成为后缀表达式
参数： const char* exp 字符串形式的中缀表达式
int* last_table 后缀表达式保存在这个int数组中
int* op_table 后缀表达式数组中 符号的位置保存在这个数组中 用来区分数字和符号
返回值： int last_num 用来保存后缀表达式表的长度
********************************************************************************************/
int transform(const char* exp, int* last_table, int* op_table)
{
int num = 0;
int last_num = 0;
int op_num = 0;
int temp = 0;
int flag = 0;
LinkStack* stack = Creat_LinkStack();//创建一个链式栈
while(‘\0‘ != exp[num])
{
while(isNumber(exp[num])) //判断是否为数字
{
temp = 10*temp + exp[num]-48;
num++;
flag = 1;
}
if(1 == flag) //只有进入了上面的循环 才可以进行下面的操作
{
last_table[last_num] = temp; //把数字保存在后缀表达式中
last_num++;
temp = 0; //temp清零
flag = 0;
if(‘\0‘ == exp[num])
{
break; //如果是最后一个数字就要跳出循环
}
}
if(isOperator(exp[num])) //判断是否为运算符
{
/*栈顶符号优先级不低的情况*/
while(priority(exp[num]) < (priority((char)(int)Get_LinkStack_Top(stack))))
{
last_table[last_num] = (char)(int)LinkStack_Pop(stack);
op_table[op_num] = last_num;
op_num++;
last_num++;
}
LinkStack_Push(stack,(void*)(int)exp[num]);
}
else if( isLeft(exp[num]) ) //判断是否为左括号
{
LinkStack_Push(stack,(void*)(int)exp[num]);
}
else if( isRight(exp[num]) ) //判断是否为右括号
{
while(!isLeft((char)(int)Get_LinkStack_Top(stack)))
{
last_table[last_num] = (char)(int)LinkStack_Pop(stack);
op_table[op_num] = last_num;
op_num++;
last_num++;
}
LinkStack_Pop(stack); // 将左括号从栈中弹出
}
else // 算式错误的情况
{
printf("Invalid expression!");
break;
}
num++;
}
/*遍历结束 把栈中的符号全部输出*/
while( (Get_LinkStack_Length(stack)>0) && (‘\0‘ == exp[num]))
{
last_table[last_num] = (char)(int)LinkStack_Pop(stack);
op_table[op_num] = last_num;
op_num++;
last_num++;
}
op_table[op_num] = -1; //负1 作为操作符表的结束
Destroy_LinkStack(stack); //销毁一个链式栈
return last_num;
}
/********************************************************************************************
函数名： print_last_table
函数功能：打印后缀表达式
参数： 后缀表达式数组 last_table 后缀表达式符号下表数组 op_table 后缀表达式长度 last_num
返回值： 无
********************************************************************************************/
void print_last_table(const int* last_table, const int* op_table, const int last_num)
{
int i = 0;
int j = 0;
for(i = 0; i<last_num; i++)
{
if(i == op_table[j])
{
printf("%c ",last_table[i]);
j++;
}
else
{
printf("%d ",last_table[i]);
}
}
printf("\n");
}
/********************************************************************************************
函数名： express
函数功能：计算左值和右值的四则运算
参数： int left 左值 int right右值 char op 运算符
返回值： 返回计算的值
********************************************************************************************/
int express(int left, int right, char op)
{
int ret = 0;
switch(op)
{
case ‘+‘:
ret = left + right;
break;
case ‘-‘:
ret = left - right;
break;
case ‘*‘:
ret = left * right;
break;
case ‘/‘:
ret = left / right;
break;
default:
break;
}
return ret;
}
/********************************************************************************************
函数名： compute
函数功能：后缀表达式计算
参数： 后缀表达式数组 last_table 后缀表达式符号下表数组 op_table 后缀表达式长度 last_num
返回值： 返回计算的值
********************************************************************************************/
int compute(const int* last_table, const int* op_table, const int last_num)
{
LinkStack* stack = Creat_LinkStack();//创建一个链式栈
int ret = 0;
int i = 0;
int j = 0;
for(i = 0; i<last_num; i++)
{
if(i == op_table[j])
{
int right = (int)LinkStack_Pop(stack);
int left = (int)LinkStack_Pop(stack);
int result = express(left, right, last_table[i]);
LinkStack_Push(stack,(void*)result);
j++;
}
else
{
LinkStack_Push(stack,(void*)last_table[i]);
}
}
/*栈中只有一个数据 且遍历完全后缀表达式数组*/
if((Get_LinkStack_Length(stack) == 1) && (last_num == i) )
{
ret = (int)LinkStack_Pop(stack);
}
else
{
printf("Invalid expression!");
}
Destroy_LinkStack(stack); //销毁一个链式栈
return ret;
}
int main(int argc, char *argv[])
{
int last_table[100] = {0}; //后缀表达式存放在这个数组中
int op_table[100] = {0}; //用来存放后缀表达式中符号的下表 -1为结束
int last_num = 0;
last_num = transform("78-(5*16)+28/2", last_table, op_table);
print_last_table(last_table, op_table, last_num);
printf("\n%d\n",compute(last_table, op_table, last_num));
return 0;
}
注意：第一，上面代码是一个可以接受多位数计算的后缀计算算法，last_table数组用来存放后缀表达式，op_table数组用来存放 last_table数组中运算符的数组下标！数据结构学习笔记(7.栈的应用及简单的计算器),布布扣,bubuko.com
原文：http://blog.csdn.net/mbh_1991/article/details/21533339