求波兰表达式的c++程序 要快！！！

include <malloc.h>

#include <stdio.h>

#include <ctype.h>//判断是否为字符的函数的头文件

#define maxsize 100

typedef int elemtype

typedef struct sqstack sqstack//由于sqstack不是一个类型 而struct sqstack才是

char ch[7]={'+','-','*','/','(',')','#'}//把符号转换成一个字符数组

int f1[7]={3,3,5,5,1,6,0}//栈内元素优先级

int f2[7]={2,2,4,4,6,1,0}//栈外的元素优先级

struct sqstack

{

elemtype stack[maxsize]

int top

}

void Initstack(sqstack *s)

{

s->top=0

}

void Push(sqstack *s,elemtype x)

{

if(s->top==maxsize-1)

printf("Overflow\n")

else

{

s->top++

s->stack[s->top]=x

}

}

void Pop(sqstack *s,elemtype *x)

{

if(s->top==0)

printf("underflow\n")

else

{

*x=s->stack[s->top]

s->top--

}

}

elemtype Gettop(sqstack s)

{

if(s.top==0)

{

printf("underflow\n")

return 0

}

else

return s.stack[s.top]

}

elemtype f(char c)

{

switch(c)

{

case '+':

return 0

case '-':

return 1

case '*':

return 2

case '/':

return 3

case '(':

return 4

case ')':

return 5

default:

return 6

}

}

char precede(char c1,char c2)

{

int i1=f(c1)

int i2=f(c2)//把字符变成数字

if(f1[i1]>f2[i2])//通过原来设定找到优先级

return '>'

else if(f1[i1]<f2[i2])

return '<'

else

return '='

}

int Operate(elemtype a,elemtype theta,elemtype b)

{

int sum

switch(theta)

{

case 0:

sum=a+b

break

case 1:

sum=a-b

break

case 2:

sum=a*b

break

default:

sum=a/b

}

return sum

}

EvaluateExpression()

{

char c

int i=0,sum=0

int k=1,j=1//设置了开关变量

elemtype x,theta,a,b

sqstack OPTR,OPND

Initstack(&OPTR)

Push(&OPTR,f('#'))//0压入栈

Initstack(&OPND)

c=getchar()

if(c==ch[2]||c==ch[3]||c==ch[5]||c==ch[6])//先对＋和-的情况忽略和左括号的情况

{

printf("错误1 \n")

k=0

return 0

}

if(c==ch[0])

c=getchar()//如果是＋，把它覆盖

if(c==ch[1])

{

j=0

c=getchar()//也把－号覆盖

}

while(c!='#'||ch[Gettop(OPTR)]!='#')

{

if(isdigit(c))

{

sum=0

while(isdigit(c))

{

if(!j)

{

sum=sum*10-(c-'0')//实现了数字串前面有负号（之前是：sum=-(sum*10)-(c-'0')结果是－12＋13＝21）

}

else

sum=sum*10+(c-'0')

c=getchar()

}

Push(&OPND,sum)//如果还是数字先不压栈，把数字串转化成十进制数字再压栈

j=1

}

else

if(k)

{

switch(precede(ch[Gettop(OPTR)],c))

{

case'<': Push(&OPTR,f(c))//把它们整型化

c=getchar()

if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c=='\n')//要除去下个是‘（’的情况 也把以运算符归到这里来

{

printf("出错2\n")

k=0

return 0//加了开关变量和返回0的值使程序更以 *** 作

}

break

case'=': Pop(&OPTR,&x)

c=getchar()

if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c=='\n')//把ch[6]的情况也忽略了但此时并没有注意到右括号后面右运算符的情况

{

printf("出错2\n")

k=0

return 0

}

break

case'>': Pop(&OPTR,θ)

Pop(&OPND,&b)

Pop(&OPND,&a)//注意这里是谁先出栈

Push(&OPND,Operate(a,theta,b))

break

}

}

}//在这里判断是否以运算符结束是不对的

return(Gettop(OPND))

}

main()

{

int result

printf("输入你的算术表达式：\n")

result=EvaluateExpression()

printf("结果是 :%d\n",result)

return 0

}

【jixingzhong】:

本计算器利用堆栈来实现。

1、定义后缀式计算器的堆栈结构

因为需要存储的单元不多，这里使用顺序栈，即用一维数组来模拟堆栈：

#define MAX 100

int stack[MAX]

int top=0

因此程序中定义了长度为MAX的一维数组，这里MAX用宏定义为常数100，我们可以修改宏定义而重新定义堆栈的大小。

整型数据top为栈顶指示，由于程序开始时堆栈中并无任何数据元素，因此top被初始化为0。

2、存储后缀式计算器的运算数

我们定义了堆栈stack[MAX]后，就可以利用入栈 *** 作存储先后输入的两个运算数。

下面看一下是如何实现的：

int push(int i) /*存储运算数，入栈 *** 作*/

{

if(top<MAX)

{

stack[++top]=i/*堆栈仍有空间，栈顶指示上移一个位置*/

return 0

}

else /*堆栈已满，给出错误信息，返回出错指示*/

{

printf("The stack is full")

return ERR

}

}

我们在调用函数push时，如果它的返回值为0，说明入栈 *** 作成功；否则，若返回值为ERR(在程序中说明为-1)，说明入栈 *** 作失败。

3、从堆栈中取出运算数

当程序中读完了四则运算符后，我们就可以从堆栈中取出已经存入的两个运算数，构成表达式，计算出结果。取出运算数的函数采用的正是出栈算法。在本例中，实现该算法的函数 为pop():

int pop()/*取出运算数，出栈 *** 作*/

{

int var/*定义待返回的栈顶元素*/

if(top!=NULL) /*堆栈中仍有数据元素*/

{

var=stack[top--]/*堆栈指示下移一个位置*/

return var

}

else /*堆栈为空，给出错误信息，并返回出错返回值*/

printf("The stack is cmpty!\n")

return ERR

}

同样，如果堆栈不为空，pop()函数返回堆栈顶端的数据元素，否则，给出栈空提示，并返回错误返回值ERR。

4、设计完整的后缀式计算器

有了堆栈存储运算数，后缀式计算器的设计就很简单了。程序首先提示用户输入第一个运算数，调用push()函数存入堆栈中；而后提示用户输入第二个运算数，同样调用push()函数存入堆栈中。接下来，程序提示用户输入+,-,*,/四种运算符的一种，程序通过switch_case结构判断输入运算符的种类，转而执行不同的处理代码。以除法为例，说明程序的执行流程：

case '/':

b=pop()

a=pop()

c=a/b

printf("\n\nThe result is %d\n",c)

printf("\n")

break

程序判断用户输入的是除号后，就执行上述代码。首先接连两次调用pop()函数从堆栈中读出先前输入的运算数，存入整型数a和b中；然后执行除法运算，结果存入单元c中。这时需要考虑究竟谁是被除数，谁是除数。由于开始我们先将被除数入栈，根据堆栈“先进后出”的原则，被除数应该是第二次调用pop()函数得到的返回值。而除数则是第一次调用pop()函数得到的返回值。

最后程序打印出运算结果，并示提示用户是否继续运行程序：

printf("\t Continue?(y/n):")

l=getche()

if(l=='n')

exit(0)

如果用户回答是"n"，那么结束程序，否则继续循环。

完整的程序代码如下：

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define ERR -1

#define MAX 100 /*定义堆栈的大小*/

int stack[MAX]/*用一维数组定义堆栈*/

int top=0/*定义堆栈指示*/

int push(int i) /*存储运算数,入栈 *** 作*/

{

if(top<MAX)

{

stack[++top]=i/*堆栈仍有空间，栈顶指示上移一个位置*/

return 0

}

else

{

printf("The stack is full")

return ERR

}

}

int pop() /*取出运算数，出栈 *** 作*/

{

int var/*定义待返回的栈顶元素*/

if(top!=NULL) /*堆栈中仍有元素*/

{

var=stack[top--]/*堆栈指示下移一个位置*/

return var/*返回栈顶元素*/

}

else

printf("The stack is empty!\n")

return ERR

}

void main()

{

int m,n

char l

int a,b,c

int k

do{

printf("\tAriothmatic Operate simulator\n")/*给出提示信息*/

printf("\n\tPlease input first number:")/*输入第一个运算数*/

scanf("%d",&m)

push(m)/*第一个运算数入栈*/

printf("\n\tPlease input second number:")/*输入第二个运算数*/

scanf("%d",&n)

push(n)/*第二个运算数入栈*/

printf("\n\tChoose operator(+/-/*//):")

l=getche()/*输入运算符*/

switch(l) /*判断运算符，转而执行相应代码*/

{

case '+':

b=pop()

a=pop()

c=a+b

printf("\n\n\tThe result is %d\n",c)

printf("\n")

break

case '-':

b=pop()

a=pop()

c=a-b

printf("\n\n\tThe result is %d\n",c)

printf("\n")

break

case '*':

b=pop()

a=pop()

c=a*b

printf("\n\n\tThe result is %d\n",c)

printf("\n")

break

case '/':

b=pop()

a=pop()

c=a/b

printf("\n\n\tThe result is %d\n",c)

printf("\n")

break

}

printf("\tContinue?(y/n):")/*提示用户是否结束程序*/

l=getche()

if(l=='n')

exit(0)

}while(1)

}

【studyall123】:

#include <stdio.h>

#include <conio.h>

#include <malloc.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status

#define STACK_INIT_SIZE 100 //初始分配量

#define STACKINCREMENT 10 //存储空间的分配增量

typedef char ElemType

typedef ElemType OperandType// *** 作数

typedef char OperatorType

typedef struct

{

ElemType *base

ElemType *top

int stacksize

}SqStack

Status InitStack(SqStack &S)

{

//构造一个空栈S

S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType))

if(!S.base) exit (OVERFLOW)

S.top = S.base

S.stacksize = STACK_INIT_SIZE

return OK

}

Status GetTop(SqStack S){

ElemType e

if (S.top == S.base) return ERROR

e = *(S.top-1)

return e

}

Status Push (SqStack &S,ElemType e)

{

//插入元素e为新的栈顶元素

if (S.top - S.base >= S.stacksize){

S.base = (ElemType *) realloc ( S.base,

(S.stacksize + STACKINCREMENT) * sizeof(ElemType))

if(!S.base) exit (OVERFLOW)

S.top = S.base + S.stacksize

S.stacksize += STACKINCREMENT

}

*S.top++ = e

return OK

}

Status Pop (SqStack &S,ElemType &e){

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR

if(S.top == S.base) return ERROR

e = * --S.top

return OK

}

char In(char c,char OP[])

{

if(c>=35 &&c<=47)

return 1

else return 0

}

char OP[8]={'+','-','*','/','(',')','#','\0'}

int m[7][7]={1,1,2,2,2,1,1,

1,1,2,2,2,1,1,

1,1,1,1,2,1,1,

1,1,1,1,2,1,1,

2,2,2,2,2,0,-1,

1,1,1,1,-1,1,1,

2,2,2,2,2,-1,0}//1 >2 <0 = -1 不存在

char Precede(char i,char j)

{

int a,bchar *p

for(p=OP,a=0*p!='\0'p++,a++)

if(*p==i) break

for(p=OP,b=0*p!='\0'p++,b++)

if(*p==j) break

if(m[a][b]==1) return '>'

else if(m[a][b]==2) return '<'

else if(m[a][b]==0) return '='

else return 'O'

}

char Operate(char a,char theta,char b)

{

if(a>47) a=atoi(&a)

if(b>47) b=atoi(&b)

switch(theta)

{

case '+': return a+b

break

case '-': return a-b

break

case '*': return a*b

break

case '/': return a/b

break

}

}

OperandType EvaluateExpression()

{

SqStack OPTR,OPND

OperandType a,b,cOperatorType theta

InitStack(OPTR)Push(OPTR,'#')

InitStack(OPND)c=getchar()

while (c!='#' || GetTop(OPTR)!='#')

{

if (!In(c,OP)){Push(OPND,c)c=getchar()}

else

switch(Precede(GetTop(OPTR),c))

{

case '<' :

Push(OPTR,c)c = getchar()

break

case '=' :

Pop(OPTR,c)c = getchar()

break

case '>' :

Pop(OPTR,theta)

Pop(OPND,b)Pop(OPND,a)

Push(OPND,Operate(a,theta,b))

break

}

}

return GetTop(OPND)

}

void main()

{

printf("(以#为结束符)\n")

printf("请输入：\n")

int a

a=(int)EvaluateExpression()

printf("%d",a)

getch()

}

【laiwusheng】:

ls都正确

【Jim_King_2000】:

C++ In Action这本书里面有表达式求值的详细项目分析.

【xlbdan】:

数据结构的书里面都有的,仔细看一下

【zpk1234】:

studyall123的只能对0到9的数字运算才有效,对于10以上的数字就不行!不知道有没有更好的方法!

【sjjf】:

现在的人，连google一下都懒啊

【aaron85】:

实际上是按照逆波兰式的顺序让输入的表达式入栈，再根据运算符优先级来计算。

【pomiox】:

lenrning!

如题，代码如下，欢迎探讨！！！

[code=C/C++][/code]

/* 表达式的后缀表示及其求值 */

#include <stdio.h>

typedef int ElemType/* 考虑到char型运算时的隐形提升会溢出，此处定义为int，代价仅浪费了内存空间 */

#define MAXNUM 16

struct stack

{

ElemType data[MAXNUM]

int top

}

void StackInit(struct stack *stack)

{

int i = 0

for(i <MAXNUMi++)

{

stack->data[i] = 0

}

stack->top = 0/* 栈底部从索引0处开始 */

}

void StackPush(struct stack *stack,ElemType c)

{

if(MAXNUM == stack->top) /* 栈中元素最多有MAXNUM - 1个 */

{

printf("The stack is full ")

return

}

stack->data[stack->top++] = c

}

ElemType StackPop(struct stack *stack)

{

if(0 == stack->top)

{

printf("The stack is empty ")/* 当栈空时，若返回0是错误的 */

return 0

}

return stack->data[--stack->top]

}

void PostfixEvaluation(struct stack *stack)

{

return/* 这个函数非常简单了，所有的麻烦都已经解决了，我实在不想完成它 */

}

int ChangeToPostfix(char *str)

{

int i = 0,flag = 0/* flag 用来标记连续数字的出现，没想到好点的办法 */

int c,ch

struct stack ch_stack

struct stack op_stack

StackInit(&ch_stack)

StackInit(&op_stack)

while( != (c = *(str + i))) /* 此处需注意的是:如果是静态的字符串，以为结束条件,如果是用户输入的，则以 ’为结束条件 */

{

if((* == c) || (/ == c) || (( == c))

{

flag = 0

StackPush(&op_stack,c)

}

else if() == c)

{

flag = 0

while(( != (c = StackPop(&op_stack)))

{

StackPush(&ch_stack,c)

}

if(0 == op_stack.top)

{

printf("the ( hasnt found when the ) come in! ")

return -1

}

}

else if((+ == c)|| (- == c))

{

flag = 0

/* +和-优先级低，运算符栈中的((如果存在)后的所有运算符需推出 */

if(0 != op_stack.top) /* 你可以不在此处添加top的检查，那样，你可以发现 StackPop错误返回的0被拾取了 */

{ /* 被逼无奈,只得在此检查top值，无法寄希望于StackPop了 */

while(( != (ch = StackPop(&op_stack)))

{

StackPush(&ch_stack,ch)

if(0 == op_stack.top)

{

break

}

}

}

StackPush(&op_stack,c)

}

else if((c >= 0) &&(c <= 9)) /* 对于表达式中2位或多位连续的数字，需特殊处理 */

{

if(0 == flag)

{

StackPush(&ch_stack,(c - 0))

flag = 1

}

else

{

StackPush(&ch_stack,10 * StackPop(&ch_stack) + (c - 0))

}

}

i++

}

while(0 != op_stack.top) /* 表达式处理结束，将运算符栈中的所有运算符推出并压入字符栈 */

{

StackPush(&ch_stack,StackPop(&op_stack))

}

PostfixEvaluation(&ch_stack)/* 该函数放在此处可能较为欠妥，可是，只要完成了任务不就OK了么，难道你会在乎？ */

/*just test */

for(i = 0i <ch_stack.topi++)

{

if(+ == ch_stack.data[i])

{

printf("+..")

}

else if(- == ch_stack.data[i])

{

printf("-..")

}

else if(* == ch_stack.data[i])

{

printf("*..")

}

else if(/ == ch_stack.data[i])

{

printf("/..")

}

else

{

printf("%d..",ch_stack.data[i])

}

}

return 0

}

int main(void)

{

char str[] = "12 + 34 * 435 - 5 / 1"

/* just test */

printf("The result should be : ")

printf("12 34 435 * + 5 1 / - [= 8] ")

if(-1 == ChangeToPostfix(str))

{

printf("ChangeToPostfix() error ")

return 1

}

return 0

}

#include<stdio.h>

#include<stdbool.h>

#include<stdlib.h>

#defineSTACK_SIZE 20

intmake_empty(void)

boolis_empty(void)

boolis_full(void)

voidpush(char )

voidpop(char )

voidstack_overflow(void)

voidstack_underflow(void)

charcontents[STACK_SIZE]= {0},top

intmain(int argc, char *argv[])

{

char ch='1'

while(ch!='q'){

make_empty()

printf("Enter an RPNexpression:")

do{

scanf(" %c",&ch)

if(ch>='1'&&ch<='9')

push(ch)

else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){

top--pop(ch)

}

else if(ch=='='){

if((top-1)==0)

pop(ch)

else

printf("Nunber notused!")

break

}

else if(ch=='\n')

else{

ch='q'break /*其它情况置为退出标志q*/

}

}

while(ch!='\n')

}

return 0

}

intmake_empty(void){

/* return top=0

}

boolis_empty(void){

return top==0

}

boolis_full(void){

return top==STACK_SIZE

}

voidpush(char ch){

if(is_full())

stack_overflow()

else

contents[top++]=ch-'0'

}

voidpop(char ch){

if(is_empty())

stack_underflow()

else

switch(ch){

case'+':contents[top-1]+=contents[top]break

case '-':contents[top-1]-=contents[top]break

case'*':contents[top-1]*=contents[top]break

case'/':contents[top-1]/=contents[top]break

case '=':printf("Value ofexpression:%d\n",(int)contents[0])break

}

}

voidstack_overflow(void){

printf("Expression is toocomplex!")

exit(EXIT_FAILURE)

}

voidstack_underflow(void){

printf("Not enough operands inexpression!")

exit(EXIT_FAILURE)

}

---