[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Mystack *Stack;
struct Mystack {
int Capacity; /* 棧的容量 */
int Top_of_stack; /* 棧頂下標 */
char *Array; /* 存放棧中元素的數組 */
};
/* 棧的創建 */
Stack CreateStack(int Max)
{
Stack S;
S = malloc(sizeof(struct Mystack));
if (S == NULL)
printf("Create stack error!\n");
S->Array = malloc(sizeof(char) * Max);
if (S->Array == NULL)
printf("Create stack error!\n");
S->Capacity = Max;
S->Top_of_stack = 0;
return S;
}
/* 釋放棧 */
void DisposeStack(Stack S)
{
if (S != NULL)
{
free(S->Array);
free(S);
}
}
/* 判斷一個棧是否是空棧 */
int IsEmpty(Stack S)
{
return !S->Top_of_stack;
}
/* 判斷一個棧是否滿棧 */
int IsFull(Stack S)
{
if (S->Top_of_stack == S->Capacity - 1)
return 1;
else
return 0;
}
/* 數據入棧 */
int Push(int x, Stack S)
{
if (IsFull(S))
printf("The Stack is full!\n");
else
S->Array[S->Top_of_stack++] = x;
}
/* 數據出棧 */
int Pop(Stack S)
{
if (IsEmpty(S))
printf("The Stack is empty!\n");
else
S->Top_of_stack--;
}
/* 將棧頂返回 */
char Top(Stack S)
{
if (!IsEmpty(S))
return S->Array[S->Top_of_stack-1];
printf("The Stack is empty!\n");
return 0;
}
/* 計算優先級 */
int getPriority(char a)
{
switch(a)
{
case '#':
return 0;
break;
case '+':
case '-':
return 1;
break;
case '*':
case '/':
return 2;
break;
case '(':
return 3;
break;
default:
break;
}
}
int main()
{
int i, len;
char str[100];
printf("Please input the Infix expression that you want to change: \n");
scanf("%s", str);
len = strlen(str);
/* 根據序列的長度來創建棧 */
struct Mystack *my_stack = CreateStack(len+1);
/* 利用‘#’是為了第一進棧時能方便統一的進行判斷 */
Push('#', my_stack);
for (i = 0; i < len; i++)
{
if ((str[i] >= '0' && str[i] <= '9') || (str[i] >= 'a' && str[i] <= 'z')) /* 操作數 */
{
printf("%c", str[i]);
}
else if (str[i] != ')' && getPriority(str[i]) > getPriority(Top(my_stack))) /* 當棧頂元素優先級比下一個操作符優先級小時，把外面的操作符直接進棧 */
{
Push(str[i], my_stack);
}
else if (str[i] != ')' && getPriority(str[i]) <= getPriority(Top(my_stack)))/* 棧頂元素優先級大於等於下一個操作符的優先級，這時要出棧，但要確保'('不出棧 */
{
while(getPriority(str[i]) <= getPriority(Top(my_stack)) && Top(my_stack) != '(' )
{
printf("%c", Top(my_stack));
Pop(my_stack);
}
Push(str[i], my_stack);
}
else if (str[i] == ')') /* 如果遇見一個右括號，那麼就將棧頂元素彈出，直至遇見一個左括號為止 */
{
while (Top(my_stack) != '(')
{
printf("%c", Top(my_stack));
Pop(my_stack);
}
Pop(my_stack);
}
}
/* 輸出棧中剩余的元素 */
if (!IsEmpty(my_stack))
{
while (Top(my_stack) != '#')
{
printf("%c", Top(my_stack));
Pop(my_stack);
}
printf("\n");
}
DisposeStack(my_stack);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Mystack *Stack;
struct Mystack {
int Capacity; /* 棧的容量 */
int Top_of_stack; /* 棧頂下標 */
char *Array; /* 存放棧中元素的數組 */
};
/* 棧的創建 */
Stack CreateStack(int Max)
{
Stack S;
S = malloc(sizeof(struct Mystack));
if (S == NULL)
printf("Create stack error!\n");
S->Array = malloc(sizeof(char) * Max);
if (S->Array == NULL)
printf("Create stack error!\n");
S->Capacity = Max;
S->Top_of_stack = 0;
return S;
}
/* 釋放棧 */
void DisposeStack(Stack S)
{
if (S != NULL)
{
free(S->Array);
free(S);
}
}
/* 判斷一個棧是否是空棧 */
int IsEmpty(Stack S)
{
return !S->Top_of_stack;
}
/* 判斷一個棧是否滿棧 */
int IsFull(Stack S)
{
if (S->Top_of_stack == S->Capacity - 1)
return 1;
else
return 0;
}
/* 數據入棧 */
int Push(int x, Stack S)
{
if (IsFull(S))
printf("The Stack is full!\n");
else
S->Array[S->Top_of_stack++] = x;
}
/* 數據出棧 */
int Pop(Stack S)
{
if (IsEmpty(S))
printf("The Stack is empty!\n");
else
S->Top_of_stack--;
}
/* 將棧頂返回 */
char Top(Stack S)
{
if (!IsEmpty(S))
return S->Array[S->Top_of_stack-1];
printf("The Stack is empty!\n");
return 0;
}
/* 計算優先級 */
int getPriority(char a)
{
switch(a)
{
case '#':
return 0;
break;
case '+':
case '-':
return 1;
break;
case '*':
case '/':
return 2;
break;
case '(':
return 3;
break;
default:
break;
}
}
int main()
{
int i, len;
char str[100];
printf("Please input the Infix expression that you want to change: \n");
scanf("%s", str);
len = strlen(str);
/* 根據序列的長度來創建棧 */
struct Mystack *my_stack = CreateStack(len+1);
/* 利用‘#’是為了第一進棧時能方便統一的進行判斷 */
Push('#', my_stack);
for (i = 0; i < len; i++)
{
if ((str[i] >= '0' && str[i] <= '9') || (str[i] >= 'a' && str[i] <= 'z')) /* 操作數 */
{
printf("%c", str[i]);
}
else if (str[i] != ')' && getPriority(str[i]) > getPriority(Top(my_stack))) /* 當棧頂元素優先級比下一個操作符優先級小時，把外面的操作符直接進棧 */
{
Push(str[i], my_stack);
}
else if (str[i] != ')' && getPriority(str[i]) <= getPriority(Top(my_stack)))/* 棧頂元素優先級大於等於下一個操作符的優先級，這時要出棧，但要確保'('不出棧 */
{
while(getPriority(str[i]) <= getPriority(Top(my_stack)) && Top(my_stack) != '(' )
{
printf("%c", Top(my_stack));
Pop(my_stack);
}
Push(str[i], my_stack);
}
else if (str[i] == ')') /* 如果遇見一個右括號，那麼就將棧頂元素彈出，直至遇見一個左括號為止 */
{
while (Top(my_stack) != '(')
{
printf("%c", Top(my_stack));
Pop(my_stack);
}
Pop(my_stack);
}
}
/* 輸出棧中剩余的元素 */
if (!IsEmpty(my_stack))
{
while (Top(my_stack) != '#')
{
printf("%c", Top(my_stack));
Pop(my_stack);
}
printf("\n");
}
DisposeStack(my_stack);
return 0;
}
測試數據：
[cpp]
shang@shang:~/C$ ./a.out
Please input the Infix expression that you want to change:
a+b*c+(d*e+f)*g
abc*+de*f+g*+
shang@shang:~/C$ ./a.out
Please input the Infix expression that you want to change:
a+b*c+(d*e+f)*g
abc*+de*f+g*+
