主题：[讨论]求助:有哪位高手能帮我看一下这道题的吗?谢谢
whj2005
[专家分：0] 发布于 2006-11-05 22:38:00
要求用链表实现堆栈，并用堆栈进行四则表达式求值。
给出一串字符，包括整数（0-9），括号（‘（’，‘）’），计算符（‘+’，‘-’，‘*’，‘/’），
所有计算顺序都由括号给出。比如 (1 * ((2+3) - 4) )
要求处理并计算最终结果：1
提示：
可以设3个堆栈，分别存放右括号（，整数，计算符。
每读到‘）’，弹出堆栈栈顶元素，处理计算，中间计算结果再压栈。
第1个堆栈
(
( ( (
( ( ( (
第2个堆栈
3 4
2 5 5 1
1 1 1 1 1
第3个堆栈
+ -
* * * *
回复列表 （共6个回复）
沙发
max810511 [专家分：170] 发布于 2006-11-06 10:05:00
typedef struct Data{
int data;
struct Data * next;
}DataType;
typedef struct Symbol{
char symbol;
struct Symbol * next;
}SymbolType,Bracket;
void pushdata(DataType *head,int value)
{ /*头插法*/
DataType * p=malloc(sizeof(DataType));
p->data=value;
p->next=head->next;
head->next=p;
}
void pushchar(SymbolType *head,char value)
{
SymbolType * p=malloc(sizeof(SymbolType));
p->symbol=value;
p->next=head->next;
head->next=p;
}
void popdata(DataType * head)
{
DataType *p=head->next;
head->next=p->next;
free(p);
}
void popchar(SymbolType * head)
{
SymbolType *p=head->next;
head->next=p->next;
free(p);
}
int topdata(DataType * head)
{ return head->next->data; }
int topdata(SymbolType * head)
{ return head->next->symbol; }
int calculate(char expression[],int n)
{
int i,x,y;char temp;
DataType * data;
SymbolType * symbol;
Bracket * bracket;
for(i=0;i<n;i++)
{
if(expression[i]>='0' && expression[i]<='9')
pushdata(data,expression[i]);
if(expression[i]=='(')
pushchar(bracket,'(');
if(expression[i]==')')
{
x=topdata(data);
popdata(data);
y=topdata(data);
popdata(data);
temp=topchar(symbol);
popchar(symbol);
popchar(bracket);
if(temp=='+') pushdata(data,x+y);
else if(temp=='-') pushdata(data,x-y);
else if(temp=='*') pushdata(data,x*y);
else if(temp=='/') pushdata(data,(int*)x/y);
}
else
pushchar(symbol,expression[i]);
}
return topdata(data);
}
板凳
雨523 [专家分：200] 发布于 2006-11-06 11:58:00
５５５５５５５，这么难啊，我简直没主意，可二楼的同学竟然还能给出程序，服啊，赞
3 楼
whj2005 [专家分：0] 发布于 2006-11-06 12:08:00
先谢谢你的回复:不过我试了还是有点错误的:
Turbo C For Windows 3.1 正在为您编译....
c:\docume~1\88\桌面\noname0.c:
警告 c:\docume~1\88\桌面\noname0.c 12: 非可移动指针转换 在函数
警告 c:\docume~1\88\桌面\noname0.c 19: 非可移动指针转换 在函数
错误 c:\docume~1\88\桌面\noname0.c 39: 'topdata'的宣告
警告 c:\docume~1\88\桌面\noname0.c 51: 可能在'data'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 53: 可能在'bracket'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 56: 可能在'data'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 57: 可能在'data'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 58: 可能在'data'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 59: 可能在'data'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 60: 可能在'symbol'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 61: 可能在'symbol'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 62: 可能在'bracket'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 63: 可能在'data'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 64: 可能在'data'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 65: 可能在'data'定义以前使用了它 在函数
错误 c:\docume~1\88\桌面\noname0.c 66: 非法指针运算 在函数
警告 c:\docume~1\88\桌面\noname0.c 66: 可能在'data'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 69: 可能在'symbol'定义以前使用了它 在函数
警告 c:\docume~1\88\桌面\noname0.c 71: 可能在'data'定义以前使用了它 在函数
*** 2 个错误 ***
4 楼
freeeerf [专家分：5440] 发布于 2006-11-06 13:14:00
这个程序什么鸟表达式都能计算:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct stackNode {
char value;
struct stackNode * nextPtr;
};
typedef struct stackNode STACKNODE;
typedef STACKNODE * STACKNODEPTR;
char *convertToPostfix (char []);
int isOperator (char c);
int precedence (char operator1,char operator2);
void push (STACKNODEPTR *topPtr, char info);
char pop (STACKNODEPTR *topPtr);
char stackTop (STACKNODEPTR topPtr);
int isEmpty (STACKNODEPTR topPtr);
void printStack (STACKNODEPTR); /*打印堆栈,多半看看堆栈是什么样子的,是否真的压进去了,或者弹出来了*/
/*下面的是用来计算后缀表达式*/
int postfix_Result(char *);
struct stackNode2 {
int data;
struct stackNode2 * nextPtr;
};
typedef struct stackNode2 STACKNODE2;
typedef STACKNODE2 * STACKNODEPTR2;
void push2 (STACKNODEPTR2 *topPtr, int info);
int pop2 (STACKNODEPTR2 *topPtr);
main()
{
char infix[30]={0},*postfix;
puts("Now, please enter your expression:");
scanf("%s",infix);
postfix=convertToPostfix (infix);
printf("%d\n",postfix_Result(postfix));
getch();
}
char *convertToPostfix (char *infix)
{
STACKNODEPTR topPtr=NULL;
int len,i,j;
static char postfix[30]={0};
char b;
push(&topPtr,'('); /*把左括号压入堆栈*/
len=strlen(infix);
infix[len]=')'; /*在infix的末端补右括号*/
for(i=0,j=0;infix[i]!='\0';i++){
if(infix[i]=='('){ /*当当前字符是左括号时,把它压入堆栈*/
push(&topPtr,'(');
continue;
}
if(infix[i]>=49&&infix[i]<=57){ /*当字符是一个数字时,就把它传给postfix*/
postfix[j++]=infix[i];
if(infix[i+1]>=49&&infix[i+1]<=57) /*如果下一个也是数字,说明非一个一位数字,于是在后面加一个','以便以后处理*/
postfix[j++]=',';
continue;
}
if(isOperator(infix[i])){ /*当是运算符时,进行不同操作*/
if(stackTop (topPtr)=='('||precedence(infix[i],stackTop (topPtr))==1){ /*当栈顶是左括号或者当前运算符比栈顶高*/
push(&topPtr,infix[i]); /*时,直接把当前运算符压入堆栈*/
}
else{
postfix[j++]=pop(&topPtr); /*栈顶字传给postfix*/
push(&topPtr,infix[i]); /*当前字符压入堆栈*/
}
continue;
}
if(infix[i]==')'){ /*如果是右符号,就不断弹出栈中运算符直到遇到左括号*/
while(1){
b=pop(&topPtr);
if(b=='(')
break; /*如果是左括号就跳出,这样就不会把左括号赋给postfix了*/
postfix[j++]=b;
}
}
}
return postfix; /*返回一个字符串首地址,与书中略有不同*/
}
int isOperator (char c) /*看是否是一个操作符*/
{
if(c==37||c==42||c==43||c==45||c==47||c==94)
return 1;
else
return 0;
}
int precedence (char operator1,char operator2) /*判断两个运算符谁的优先级高*/
{
if(operator1==43||operator1==45)
operator1=1;
if(operator1==42||operator1==47||operator1==37)
operator1=2;
if(operator1==94)
operator1=3;
if(operator2==43||operator2==45)
operator2=1;
if(operator2==42||operator2==47||operator2==37)
operator2=2;
if(operator2==94)
operator2=3;
if(operator1<operator2)
return -1;
if(operator1==operator2)
return 0;
if(operator1>operator2)
return 1;
else
return -9; /*编译器出现not all control paths return a value的报文,所以在这里返回一个-9 */
}
void push (STACKNODEPTR *topPtr,char info) /*将一个字符压入堆栈*/
{
STACKNODEPTR newPtr;
newPtr=malloc(sizeof(STACKNODE));
if(newPtr!=NULL){
newPtr->value=info;
newPtr->nextPtr=*topPtr;
*topPtr=newPtr;
}
else
printf("马的,没内存了!");
}
char pop (STACKNODEPTR *topPtr) /*弹出栈顶的字符*/
{
STACKNODEPTR tempPtr;
char popValue;
tempPtr=*topPtr;
popValue=(*topPtr) ->value;
*topPtr=(*topPtr) ->nextPtr;
free(tempPtr);
return popValue;
}
5 楼
freeeerf [专家分：5440] 发布于 2006-11-06 13:14:00
char stackTop (STACKNODEPTR topPtr) /*返回栈顶的字符,但不弹出最上面的一个结构*/
{
return topPtr->value;
}
int isEmpty (STACKNODEPTR topPtr) /*看是否堆栈为空*/
{
return topPtr==NULL; /*若成立则返回1*/
}
void printStack (STACKNODEPTR topPtr) /*打印堆栈*/
{
if(topPtr==NULL)
printf("List is empty.\n\n");
else{
printf("The list is:\n");
while(topPtr!=NULL){
printf("%c--->",topPtr->value);
topPtr=topPtr->nextPtr;
}
printf("NULL\n\n");
}
}
int postfix_Result(char *postfix)
{
STACKNODEPTR2 topPtr=NULL;
int x,y,i,j,result,n,toHigh; /* n用来记住逗号的个数*/
for(i=0;postfix[i]!='\0';i++){
if(postfix[i]>=49&&postfix[i]<=57){
for(j=i+1,n=0;postfix[j]==',';j+=2) /* 记下逗号的个数为n */
++n;
for(j=0,toHigh=1;j<n;j++) /*当是一个二位数或是三位数时,记下需乘的倍数*/
toHigh*=10;
for(result=0;n>=0;--n,i+=2,toHigh/=10)
result=result+(postfix[i]-48)*toHigh; /*计算总值并存入result,并将i的值相应增加*/
i-=2; /*由于上面执行了i+=2,故在此减 2 */
push2(&topPtr,result); /*将结果压入堆栈*/
}
else{
x=pop2(&topPtr);
y=pop2(&topPtr);
switch(postfix[i]){
case '+':
result=y+x;
break;
case '-':
result=y-x;
break;
case '*':
result=y*x;
break;
case '/':
result=y/x;
break;
case '%':
result=y%x;
break;
case '^':
result=1;
for(i=0;i<x;i++)
result*=y;
break;
}
push2(&topPtr,result);
}
}
return pop2(&topPtr);
}
void push2 (STACKNODEPTR2 *topPtr,int info) /*将一个字符压入堆栈*/
{
STACKNODEPTR2 newPtr;
newPtr=malloc(sizeof(STACKNODE2));
if(newPtr!=NULL){
newPtr->data=info;
newPtr->nextPtr=*topPtr;
*topPtr=newPtr;
}
else
printf("乱机子,没内存了!");
}
int pop2 (STACKNODEPTR2 *topPtr) /*弹出栈顶的数字*/
{
STACKNODEPTR2 tempPtr;
int popValue;
tempPtr=*topPtr;
popValue=(*topPtr) ->data;
*topPtr=(*topPtr) ->nextPtr;
free(tempPtr);
return popValue;
}
6 楼
max810511 [专家分：170] 发布于 2006-11-06 13:44:00
To楼主：我给出的只是大致的算法，如果要编译执行还需你自己的修改。
我来回复
您所在位置：