主题：求助:大哥大姐们，帮个忙啊!帮我看一下这道题.谢谢
whj2005
[专家分：0] 发布于 2006-11-06 12:17:00
要求用链表实现堆栈，并用堆栈进行四则求表达式 (((2*(1+(8-4)))-8)/2)值。可以设3个堆栈，分别存放右括号（，整数，计算符。
每读到‘）’，弹出堆栈栈顶元素，处理计算，中间计算结果再压栈。
这是头程序:下面的不会做了.帮忙喔
main()
{ int result;
char str="(((2*(1+(8-4)))-8)/2)";
result=process(str);
printf("%d\n",result);
}
int process(char *str)
{.........
回复列表 （共5个回复）
沙发
freeeerf [专家分：5440] 发布于 2006-11-06 13:10: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 */
}
板凳
freeeerf [专家分：5440] 发布于 2006-11-06 13:10:00
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;
}
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;
}
3 楼
freeeerf [专家分：5440] 发布于 2006-11-06 13:12:00
在自己未动脑袋之前看别人的程序是没有半点好处的,只会增长你的依赖性.
4 楼
freeeerf [专家分：5440] 发布于 2006-11-06 13:43:00
忽然发现这个程序有个小BUG就是当最后一个数的最后一位是0的时候,这个0竟然被忽略了,你试试.
5 楼
whj2005 [专家分：0] 发布于 2006-11-06 22:58:00
这个太复杂了..能不能就我的题写一个呢.谢谢.我的题都用括号括起来了...
我来回复
您所在位置：