－括號匹配
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如果是運算符')'，則出棧所有'('之前的棧元素，'('出棧，但不加入最終表達式。
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
