问一个比较有意思的问题
题目：用C实现：输入“(1+6)/(3*(3+7-1))+2=”回车输出计算结果
前几天看到过用栈的方法，但是如果涉及到()的话，就非常复杂了
于是就想是否可以用宏？比如：
#define ADD +
#define SUB -
#define ONE 1
#define TWO 2
int a;
a = ONE ADD TWO SUB ONE;
但是输入是动态输入，这就产生问题了，如何动态把这些宏连接起来呢？是否可以在运行期创建和使用宏呢？
如果修改C解释器是否可以实现呢？
我是菜鸟，请高手赐教
[解决办法]
呵呵，有点AI的味道了
[解决办法]
逆波兰式可以实现
查查数据结构
typedef int SElemType;
typedef struct SqStack
{ char *base;
char *top;
char stacksize;
}SqStack;
程序
void InitStack (SqStack &S)
{
S.base=(char *) malloc (STACK_INIT_SIZE *sizeof(char));
if (!S.base)
exit (OVERFLOW); //为栈S分配存储空间失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
int Push(SqStack &S,char ch)
// 将元素e插入到栈S中，成为新的栈顶元素
{
if (S.top-S.base> S.stacksize) //Stack==full?
{ S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT *sizeof(char)));
if (!S.base)
{ printf(“Failure to reallocate the Memory units!:\n”);
exit(OVERFLOW);
}
S.top=S.base+S.stacksize; //To Modify pointer of Satck top
S.stacksize+=STACKINCREMENT; //To modify the size of stack
} // end of if
*S.top++=ch; //先将e送入栈顶指针所指向的单元，再将栈顶指针加1
return(OK);
} //end of Push() subfunction
int Pop(SqStack &S,char &ch)
{
if (S.top==S.base)
{
printf(“下溢！”)；
return (ERROR);
}
ch=*--S.top;
return (OK);
}
void Translation()
{//将算术表达式转化为逆波兰表达式，num为算术表达式的字符总个数
int i,j;
char str[100],exp[100],ch;
SqStack S;
InitStack(S);
i=1;
printf(“ 请输入算术表达式字符串，求其逆波兰表达式，以＃为结束标志，如a-b*c/(3+6)#:\n”);
do
{
scanf(“%c”,&str);
i++;
}while(str[i-1]!=’#’);
str[0]=’(‘; //将表达式放在（）内
str[i-1]=’)’;
str=’#’;
i=0;
j=0;
while(str!=’#’)
{ if((str> =’0’ &&str <=’9’)||(str> =’a’ &&str <=’z’))
{
exp[j]=str;
j++;
} //end of if
else if(str==”(”)
Push(S.str);
else if(str==’)’)
{ while(*(S.top-1)!=’(’)
//将S中左括弧“（”以前的所有字符依次弹出并存入数组exp中
{ Pop(S,ch); exp[j]=ch; j++; }
S.top--;
} //end of elseif
else if(str==’+’||str==’-’) //如果判定为“＋”号或“-”号，则做如下操作
{ while((s.top!=S.base)&&(*(S.top-1)!=’(’))
//将S中左括弧“（”以前字符依次弹出并存入数组exp 中
{ Pop(S,ch); exp[j]=ch; j++; }
Push(S,str);
} //end of else if
else if (str==’*’||str==’/’)
{
while((*(S.top-1)==’*’)||(*(S.top-1)==’/’))
{ Pop(S,ch); exp[j]=ch; j++; }
Push(S,str);
} //end of else if
i++;
} //end of while
exp[j]=’#’;
printf(“\n\n输入的算术表达式”);
i=1;
while(str[i+1]!=’#’)
{ printf(“%c”,str);
i++;
} //end of while
printf(“ 逆波兰表达式为：\n”);
i=0;
while(exp!=’#’)
{ printf(“%c”,exp); i++; }
}
void main()
{
Translation();
printf(“\n”);
printf(“…OK…!”)
getch();
}
[解决办法]
运算对象栈dst 和运算符栈ost。逐个读入单词，其中：
——遇运算对象，直接压入dst
——遇运算符o，与ost 栈顶o ' 比较。o ' 优先级不低于o 时弹出o '，从dst 弹出运算对象，计算结果压入dst。反复至栈顶运算符优先级低于o 时将运算符o 压入ost
——遇左括号，直接进栈ost
——遇右括号，逐个弹出运算符，从dst 弹出运算对象，计算并将结果压入dst，直至把对应左括号弹出
——遇表达式结束，逐个弹出运算符并进行计算，直至处理完全部运算符
——若ost 只有一个元素则完成并输出，否则表达式有错。
[解决办法]
必然要用到栈。。。
用栈多简单啊，有括号也是一样
我看到有些人用两个栈来实现
我觉得这样程序浪费存储空间而且程序执行效率也不高
因为栈是要存储空间的，如果你用STL的Stack
你要知道它是用 Deque来实现的
而且在入栈和出栈的时候都需要函数调用的
算法思想：
将操作符分为两个级别，+和-为低优先级；*和/为高优先级。
对于操作符的数目，我按照五种情况处理。第一种为既无操作
符，有又无数字；第二种为无操作符，但是有数字；第三种是有
一个操作符；第四种为有两个操作符；第五种为三个或则三个以
上的操作符。
对于第一种情况的处理是，直接退出程序。
对于第二种情况的处理是，直接输出数值。
对于第三种情况的处理是，直接进行运算。
对于第四种情况的处理是，按照两个操作符的优先级进行运算。
对于第五种情况的处理是，先取出三个操作符和三个操作数，
按照优先级对操作数进行运算，如此循环知道字符串的结束位置
代码：
/**************************************************
* 文 件 名： Compute_string.cpp
* 文件描述： 计算一个字符串的实现文件
* 创 建 人： 刘基伟
* 创建日期： 2007年 5月 19日
* 版 本 号： 1.0
* 修改纪录： 暂无
*************************************************/
/**************************************************
* *
* 加载头文件 *
* *
**************************************************/
#include <iostream>
using namespace std;
/**************************************************
* *
* 预处理命令 *
* *
**************************************************/
#define LOW 0
#define HIGH 1
#define MULTIPLY 42
#define PLUS 43
#define SUBTRACT 45
#define DIVIDE 47
/*=========================================================
* 函 数 名： Compute_priority(const char, int &)
* 参数说明： chOperator 操作符
irefOperator_opt_flag 操作符的优先级
* 功能描述： 计算chFirst_opt的优先级
* 返 回 值： void
==========================================================*/
void Compute_priority(const char chOperator, int &irefOperator_opt_flag)
{
if((chOperator == '+ ') || (chOperator == '- ')) // 重新计算第一操作符的优先级
{
irefOperator_opt_flag = LOW;
}
else
{
irefOperator_opt_flag = HIGH;
}
}
/*=========================================================
* 函 数 名： Compute(const char, float&, float&)
* 参数说明： chOperator 第一操作符
frefFirst_value 第一操作数的引用
rrefSecond_value 第二操作数的引用
* 功能描述： 处理frefFirst_value和frefSecond_value
* 返 回 值： void
==========================================================*/
void Compute_tow_value(const char chOperator, float &frefFirst_value, float &frefSecond_value)
{
switch((int)chOperator) // 计算第一操作数
{
case MULTIPLY:
frefFirst_value *= frefSecond_value;
break;
case PLUS:
frefFirst_value += frefSecond_value;
break;
case SUBTRACT:
frefFirst_value -= frefSecond_value;
break;
case DIVIDE:
frefFirst_value /= frefSecond_value;
break;
default:
break;
}
}
[解决办法]
呵呵.
用栈当然可以解决了.
不过不用栈也可以解决,实现方法比用栈要巧妙得多---那就是递归.