#include <string.h>
int main()
{
double d[100], *dp = d
int m, k
char t[50], *tp = t
char s[100], *c = s
char* op = "+-*/"
char* fg = "0123456789."
gets(s)
while(*c) {
if(strchr(op, *c)) {
*tp++ = *c
k = 0
}else
if(strchr(fg, *c)) {
sscanf(c, "%lf%n", dp++, &m)
c += m - 1
++k
}
++c
while((dp - d >1 &&k == 2) || !*c &&dp - d >= 1) {
switch(*--tp) {
case '+': dp[-2] = dp[-2] + dp[-1]break
case '-': dp[-2] = dp[-2] - dp[-1]break
case '*': dp[-2] = dp[-2] * dp[-1]break
case '/': dp[-2] = dp[-2] / dp[-1]break
}
--dp
}
}
printf("%f", *dp)
}
#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)
}
这个问题可以分为3部分1、输入一个字符串，将其格式化的储存在一个数组中，以方便的记录表达式中数和各个符号的出现顺序
约定在数组中记录时，每个数或符号用两个整数来记录
第一个整数记录该位是什么东西，0表示是一个数，1表示是括号，2表示反括号，3、4、5、6分别表示乘除加减号
如果该位是一个数，那么第二个整数记录着个数的具体取值，否则记录该位的符号的ASCII码
比如字符串"(1-23)"会被转化成二位数组 , , , , }
这个转化过程每什么技巧性，对原字符串各位顺次判断并处理即可
原先的字符串中可能出现一元运算符正号'+'和负号'-'，为了处理方便，一律在其前面加个0，改写成"0+..."或者"0-..."
另外为了之后转化逆波兰表达式方便，处理过程中会在转化出的数组的首尾一律添加一对括号
2、将之前所提到的格式数组转化为逆波兰表达式
约定依然用二位数组记录一个逆波兰表达式，并且格式与之前的数组相同，除了没有括号以外
比如逆波兰表达式 1 2 - 35 +，会被记录成{ , , , , }
转化时，需要用一个栈
具体转化操作如下：
顺次处理格式数组的每一位，对其作判断
如果该位是一个数或者是括号'('，，将其入栈
如果该位是乘号'*'或者除号'/'，不断进行出栈操作直到栈顶元素是个括号'('或者加号'+'或者减号'-'，然后将这个乘号或者除号入栈
如果该位是加号'+'或者减号'-'，不断进行出栈操作直到栈顶元素是个括号'('，然后将这个加号或者减号入栈
如果该位是反括号')'，那么不断进行出栈操作直到有一个括号'('出栈
在上述操作中，所有的出栈元素，除了括号'('以外，都被顺次添加到所要生成的逆波兰表达式的末尾
这样就转化出了一条逆波兰表达式
3、对逆波兰表达式求值
求值时，也需要用到一个栈
求值步骤如下：
顺次处理逆波兰表达式的每一位，对其作判断
如果该位是一个数，将这个数入栈
如果该位是一个运算符，那么连续进行两次出栈操作，可以得到栈顶的两个元素，对这两个元素用该位的运算符做运算，将所得的结果入栈
比如，如果当时栈顶元素是3，次栈顶的元素是2，运算符是减号'-'，那么连续两次出栈得到3和2两个元素，再将2-3的运算结果1入栈
注意有些运算符(减号和除号)不符合交换律，因此运算时必须是次栈顶元素在前、栈顶元素在后，顺序不能反
当每一位都处理完了之后，只要输入的是一个合法的逆波兰表达式，必然栈中只剩下一个元素，这个元素就是逆波兰表达式求值的结果
源代码如下：
#include <stdio.h>
#include <ctype.h>
void transform(char *str,int a[][2],int *n)
//将输入的字符串转化为格式化的数组以记录输入的表达式，str为输入的字符串，a为目标数组，n记录数组a的大小
{
int i
*n=1
a[0][0]=1
a[0][1]='('//在表达式首添加一个括号
for (i=0str[i])
{
if (isdigit(str[i]))
{
a[*n][0]=0
a[*n][1]=0
while (isdigit(str[i]))
{
a[*n][1]=a[*n][1]*10+str[i]-'0'
i++
}
}
else
{
if (str[i]=='(') a[*n][0]=1
else if (str[i]==')') a[*n][0]=2
else if (str[i]=='*') a[*n][0]=3
else if (str[i]=='/') a[*n][0]=4
else if (str[i]=='+' || str[i]=='-')
{
if (i==0 || (!isdigit(str[i-1]) &&str[i-1]!=')'))
{
a[*n][0]=0
a[*n][1]=0
(*n)++
}
if (str[i]=='+') a[*n][0]=5
else a[*n][0]=6
}
a[*n][1]=str[i]
i++
}
(*n)++
}
a[*n][0]=2
a[*n][1]=')'//在表达式尾添加一个反括号
(*n)++
}
void poland(int a[][2],int n,int p[][2],int *m)
//将格式化数组转化为逆波兰表达式，a为输入的数组，n为其长度，p为输出逆波兰表达式的目标，m记录逆波兰表达式的长度
{
int i
int stack[1000]//转化所用的栈
int depth//栈的深度
depth=0
*m=0
for (i=0i<ni++)
{
if (a[i][0]==0) stack[depth++]=i
else if (a[i][0]==1) stack[depth++]=i
else if (a[i][0]==2)
{
while (a[stack[depth-1]][0]!=1)
{
depth--
p[*m][0]=a[stack[depth]][0]
p[*m][1]=a[stack[depth]][1]
(*m)++
}
depth--
}
else if (a[i][0]==3 || a[i][0]==4)
{
while (a[stack[depth-1]][0]==0 || a[stack[depth-1]][0]==3 || a[stack[depth-1]][0]==4)
{
depth--
p[*m][0]=a[stack[depth]][0]
p[*m][1]=a[stack[depth]][1]
(*m)++
}
stack[depth++]=i
}
else if (a[i][0]==5 || a[i][0]==6)
{
while (a[stack[depth-1]][0]!=1)
{
depth--
p[*m][0]=a[stack[depth]][0]
p[*m][1]=a[stack[depth]][1]
(*m)++
}
stack[depth++]=i
}
}
}
void print_poland(int p[][2],int m)
//打印逆波兰表达式，p为逆波兰表达式，m为表达式长度
{
int i
for (i=0i<mi++)
{
if (p[i][0]==0) printf("%d",p[i][1])
else printf("%c",p[i][1])
}
putchar('\n')
}
double evaluate(int p[][2],int m)
//对逆波兰表达式求值，p为逆波兰表达式，m为表达式长度
{
double stack[1000]//求值所用的栈
int depth//栈的深度
int i
depth=0
for (i=0i<mi++)
{
if (p[i][0]==0) stack[depth++]=p[i][1]
else
{
double a,b
b=stack[--depth]
a=stack[--depth]
if (p[i][0]==3) stack[depth++]=a*b
else if (p[i][0]==4) stack[depth++]=a/b
else if (p[i][0]==5) stack[depth++]=a+b
else stack[depth++]=a-b
}
}
return stack[0]
}
int a[1000][2]
int n
int p[1000][2]
int m
main()
{
transform("5*(8-2)+9",a,&n)
poland(a,n,p,&m)
print_poland(p,m)
printf("The result of the expression is %lf\n",evaluate(p,m))
return
}
