栈相关算法

－括号匹配

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如果是运算符')'，则出栈所有'('之前的栈元素，'('出栈，但不加入最终表达式。