控制台程序求解有理式（带括号，适用于int类型）
C++中计算有理式
第一步，将有理式以字符串的形式输入
第二步，使用string.at()函数逐个读取有理式字符串中的字符，将数字拼在一起构成操作数，然后将操作数和操作符依次存放在一个链表中
第三步，进入有理式计算算法
（只是一般的计算算法，至于开头出现括号，出现浮点数，操作数字符串转int或double类型等等，不做进一步解释）
1、 定义两个栈，分别保存操作数和操作符
2、 定义一个判定操作符优先级的函数value(string c1,string c2)，这里由于程序需要，将操作符类型定义为string类型。
符号共有+ - * / ( ) =等7种，操作符之间的优先级为：
|
Value |
c2 |
+ |
- |
* |
/ |
( |
) |
= |
|
c1 |
|
|||||||
|
+ |
1 |
1 |
-1 |
-1 |
0 |
1 |
1 |
|
|
- |
1 |
1 |
-1 |
-1 |
0 |
1 |
1 |
|
|
* |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
/ |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
( |
0 |
0 |
0 |
0 |
0 |
0 |
—— |
|
数字1代表c1可以进行优先运算，-1代表c2优先级更高，0代表什么都不做，继续输入操作数即可。
3、 依次pop有理式链表中的操作数（符）进来，当检测到链表中仅剩一个 = 时，推出程序显示计算结果。
4、 遵循左算优先的原则，当某个操作数push进操作数栈后进行判断，如果value(c1,c2)<1，那么直接回到3；如果value(c1,c2)==1，那么进入5。
5、 判断此时c1是否为（，若是，就pop掉操作符栈；否则，pop出操作数栈的两个数，进行运算，然后pop掉操作符，然后回到3；
附程序：
//stack_eqution.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <string>
#include <sstream>
#include <iostream>
using namespace std;
//单节点定义
typedef struct nnode *PtonNode;
typedef struct nnode
{
int a;
PtonNode next;
}stack1,*s1;
typedef struct onode *PtooNode;
typedef struct onode
{
string a;
PtooNode next;
}stack2,*s2;
//进栈函数
void push(intx, s1 y)
{
s1 p = new stack1;
p->a = x;
p->next = y->next;
y->next = p;
}
void push(stringx, s2 y)
{
s2 p = new stack2;
p->a = x;
p->next = y->next;
y->next = p;
}
//出栈函数
int pop(s1y)
{
s1 z = new stack1;
z = y->next;
y->next = z->next;
int x = z->a;
free(z);
return x;
}
string pop(s2y)
{
s2 z = new stack2;
z = y->next;
y->next = z->next;
string x = z->a;
free(z);
return x;
}
//string转数字类型（int,float,double）
template <classtype>
type stringtonum(conststring& str)
{
istringstream s2num(str);
type num;
s2num >> num;
return num;
}
//操作符比较
int value(stringcl,stringcr)
{
int level;
if (cl =="+" | cl =="-")
{
if (cr =="(")
level = 0;
else if (cr == "*" | cr == "/")
level = -1;
else
level = 1;
}
else if (cl == "*" | cl == "/")
{
if (cr =="(")
level = 0;
else
level = 1;
}
else if (cl == "(")//当cl出现（或者）时，
{
if (cr ==")")
level = 1;
else
level = 0;
}
else
level = 0;
return level;
}
//进队列函数
void pushh(stringx, s2 y)
{
s2 p = y;
while (p->next != NULL)
{
p = p->next;
}
s2 z = new stack2;
z->a = x;
z->next = p->next;
p->next = z;
}
//多项式字符串入栈
int into_stack(s2equation, strings)
{
int i = 0;
string str1;
while (s.length() != 0)
{
while (s.at(i) !='+' & s.at(i) !='-' & s.at(i) !='*' & s.at(i) !='/' & s.at(i) !='(' & s.at(i) !=')' & s.at(i) !='=')
{
str1 += s.at(i);
i++;
if (s.at(i) =='+' | s.at(i) =='-' | s.at(i) =='*' | s.at(i) =='/' | s.at(i) =='(' | s.at(i) ==')' | s.at(i) =='=')
{
pushh(str1, equation);
str1 = "";
}
}
if (s.at(i) =='+' | s.at(i) =='-' | s.at(i) =='*' | s.at(i) =='/' | s.at(i) =='(' | s.at(i) ==')' | s.at(i) =='=')
{
str1 = "";
str1 += s.at(i);
pushh(str1, equation);
str1 = "";
if (s.at(i) =='=')
{
str1 += s.at(i);
break;
}
else
{
i++;
}
}
if (str1 == "=")
{
break;
}
}
// if (s.length() == 0)
// {
// cout << "无多项式输入" << endl;
// return 0;
// }
return 1;
}
//内部运算函数
int compute(s2equ)
{
s1 numhead = new stack1; numhead->next = NULL;
s2 operhead = new stack2; operhead->next = NULL;
if (equ->next ==NULL)
{
cout << endl << "无多项式输入" << endl << endl;
return 0;
}
if (equ->next->a =="=")
{
cout << endl << "无多项式输入" << endl << endl;
return 0;
}
string str1 = pop(equ);//用于过程中储存equ中的字符串
int nl, nr;//用于过程中操作数的储存
if (str1 != "+"&str1 != "-"&str1 != "*"&str1 != "/"&str1 != "("&str1 != ")"&str1 != "=")
push(stringtonum<int>(str1),numhead);
else
push(str1, operhead);
while (equ->next->a !="=")
{
str1 = pop(equ);
if (str1 != "+"&str1 != "-"&str1 != "*"&str1 != "/"&str1 != "("&str1 != ")"&str1 != "=")
{
push(stringtonum<int>(str1),numhead);
while(value(operhead->next->a,equ->next->a) == 1)
{
if(operhead->next->a =="(")
{
pop(operhead);
pop(equ);
if (operhead->next==NULL)
break;
continue;
}
nr = pop(numhead);
nl = pop(numhead);
if(operhead->next->a =="+")
{
push(nl+nr, numhead);
}
if(operhead->next->a =="-")
{
push(nl - nr, numhead);
}
if(operhead->next->a =="*")
{
push(nl * nr, numhead);
}
if(operhead->next->a =="/")
{
if (nr == 0)
{
cout << endl<< "多项式有误，除数出现0" << endl << endl;
return 0;
}
push(nl / nr, numhead);
}
pop(operhead);
if (operhead->next==NULL)
break;
}
}
else
{
push(str1, operhead);
if (str1 == ")")
pop(operhead);
}
}
cout << numhead->next->a<<endl;
return 0;
}
int _tmain(int argc,_TCHAR* argv[])
{
//多项式输入
cout <<"输入多项式，以=结尾:" << endl;
string str;
getline(cin, str);
//多项式入队列
s2 equ = new stack2; equ->next = NULL;
into_stack(equ, str);
//多项式运算（使用栈）
compute(equ);
return 0;
}