其实真正想做一个好的计算器会用到编译原理状态机、状态转换相关知识，这里我仅仅是对一些我能想到的情况进行了处理，还会有很多想不到的情况，编程任重而道远。
数据结构题目：栈
题目：算术表达式求值
输入中缀算术表达式，如：5+(4-2)3，将其转换成后缀表达式并输出：542-3+，再对后缀表达式求值（本例结果为11）并将结果输出。
image
c:
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "stdlib.h"
#define ERROR 0
#define SIZE 100
int temp=0;
int error=0;
typedef struct
{
char data[SIZE];
int top;
int base;
}slink_c;
typedef struct
{
double data[SIZE];
int top;
int base;
}slink_d;
void Initstack_c(slink_c *s)
{
s->top = 0;
s->base = 0;
}
void Initstack_d(slink_d *s)
{
s->top = s->base = 0;
}
int Emptystack_c(slink_c *s)
{
if(s->top == s->base)
return(1);
else
return(0);
}
int Emptystack_d(slink_d *s)
{
if(s->top == s->base)
return(1);
else
return(0);
}
char Pop_c(slink_c *s)
{
char e;
if(s->data[s->top]=='#')
return ERROR;
else
{
e=s->data[s->top-1];
s->top--;
}
return e;
}
double Pop_d(slink_d *s)
{
double e;
if(s->base == s->top)
return ERROR;
else
{
e=s->data[s->top-1];
s->top--;
}
return e;
}
void Push_c(slink_c *s, char e)
{
s->data[s->top]=e;
s->top++;
}
void Push_d(slink_d *s, double e)
{
s->data[s->top]=e;
s->top++;
}
char Gettop_c(slink_c *s)
{
if(s->top == s->base)
return ERROR;
return (s->data[s->top-1]);
}
double Gettop_d(slink_d *s)
{
if(s->top == s->base)
return ERROR;
return (s->data[s->top-1]);
}
//判断是不是一个数字
bool IsNumber(char x)
{
if(x == '0' || x == '1' || x == '2' || x == '3' || x == '4' || x == '5' || x == '6' || x == '7' || x == '8' || x == '9')
return (true);
else
return (false);
}
//判断是不是一个符号
bool IsOperator(char x)
{
if(x == '+' || x == '-' || x == '*' || x == '/' || x == '(' || x == ')'|| x == '#')
return (true);
else
return (false);
}
//符号优先级比较
int Precede (char x, char y)
{
switch(x)
{
case '(':x=0;break;
case '+':
case '-':x=1;break;
case '*':
case '/':x=2;break;
}
switch(y)
{
case '+':
case '-':y=1;break;
case '*':
case '/':y=2;break;
case '(':y=3;break;
}
if (x >= y)
return (1);
else
return (0);
}
//中缀转后缀
void mid_post(char post[], char mid[])
{
slink_c s1;
int i=0, j=0;
char ch;
Initstack_c(&s1);
Push_c(&s1,'#');
if(mid[i] == '\0')
{
error = 1;
printf("输入错误\n");
return;
}
while(mid[i]!='\0')
{
if(IsNumber(mid[i]))
{
while((mid[i] >= '0'&&mid[i] <= '9')||mid[i] == '.')
{
post[j++] = mid[i];
temp++;
i++;
}
post[j++] = ' ';
temp++;
}
else if(IsOperator(mid[i]))
{
switch(mid[i])
{
case '(':
{
i++;
if(mid[i] == '-')
{
while(mid[i] != ')')
{
post[j++] = mid[i];
i++;
temp++;
}
post[j++] = ' ';
i++;
temp++;
}
else
{
i--;
Push_c(&s1,mid[i]);
i++;
}
}break;
case ')':
{
ch = Pop_c(&s1);
do
{
post[j++] = ch;
temp++;
post[j++] = ' ';
temp++;
ch = Pop_c(&s1);
}while(ch != '(');
i++;
}break;
default :
{
while(Precede(Gettop_c(&s1),mid[i]))
{
post[j++] = Pop_c(&s1);
temp++;
post[j++] = ' ';
temp++;
}
Push_c(&s1,mid[i]);
i++;
}break;
}
}
else if(mid[i] == ' ')
{
i++;
}
else
{
error = 1;
printf("输入错误\n");
break;
return;
}
}
while(Gettop_c(&s1) != '#')
{
post[j++] = Pop_c(&s1);temp++;
post[j++] = ' ';temp++;
}
}
//单独表达式求值
double Operate(double a, char t, double b)
{
switch(t)
{
case '+': return a+b; break;
case '-': return a-b; break;
case '*': return a*b; break;
case '/':
{
if(b == 0)
{
printf("除数为0，输入错误\n");
return ERROR;
}
return a/b;
break;
}
default:
{
printf("输入错误\n");
return ERROR;
}
}
}
//后缀表达式求值
double postcount(char post[])
{
slink_d s2;
Initstack_d(&s2);
char ch;
int i=0,step=0,j=0;
double a=0,s=0,b=0;
ch = post[0];
while(i<temp-1)
{
if(IsNumber(post[i]))
{
s=0;
a=0;b=0;step=0;
while(post[i]>='0'&&post[i]<='9'&&post[i]!='.'&&post[i]!=' ')
{
s=10*s+post[i]-48;
i++;
}
if(post[i] == '.')
{
i++;
while(post[i]>='0'&&post[i]<='9'&&post[i]!=' ')
{
b=10*b+post[i]-48;
i++;
step++;
}
for(j=0; j<step; j++)
{
b=b/10;
}
}
a=s+b;
Push_d(&s2,a);
ch=post[++i];
}
if(IsOperator(post[i]))
{
if(post[i] == '-')
{
i++;
if(post[i]>'0'&&post[i]<'9')
{
s=0;
a=b=step=0;
while(post[i]>='0'&&post[i]<='9'&&post[i]!='.'&&post[i]!=' ')
{
s=10*s+post[i]-48;
i++;
}
if(post[i] == '.')
{
i++;
while(post[i]>='0'&&post[i]<='9'&&post[i]!=' ')
{
b=10*b+post[i]-48;
i++;
step++;
}
for(j=0; j<step; j++)
{
b=b/10;
}
}
a=-(s+b);
Push_d(&s2,a);
ch=post[++i];
}
else
{
b=Pop_d(&s2);
a=Pop_d(&s2);
Push_d(&s2,Operate(a,ch,b));
i+=1;
ch = post[i];
}
}
else
{
b=Pop_d(&s2);
a=Pop_d(&s2);
Push_d(&s2,Operate(a,ch,b));
i+=2;
ch = post[i];
}
}
}
return (Gettop_d(&s2));
}
int main()
{
char mid[100];
char post[100];
char c;
double val;
printf("请输入想要计算的中缀表达式\n:");
gets(mid);
printf("\n%s = \n",mid);
mid_post(post, mid);
if(error == 0)
{
for(int k=0;k<temp;k++)
printf("%c",post[k]);
printf("=\n");
}
else
printf("请检查您的输入\n");
if(error == 0)
{
val = postcount(post);
printf("%lf\n",val);
}
return 0;
}
java:
import java.util.Scanner;
import java.util.Stack;
/**
*@author movis
*/
public class Main {
static boolean errorflag = true; //检错旗帜，检验是否输入违法
public static void main(String[] args) {
String input;
StringBuffer stmp;
String mid ;
String post;
double output = 0;
String cont; //继续旗帜，控制是否继续
Scanner in = new Scanner(System.in);
do {
stmp = new StringBuffer("");
System.out.println("请输入表达式:");
input = in.nextLine();
//删除输入中多余的空格
for(int i=0; i<input.length(); i++) {
if(!IsNumber(input.charAt(i)) && !IsOperator(input.charAt(i)))
errorflag = false;
if(input.charAt(i) != ' ')
stmp.append(input.charAt(i));
}
if(!errorflag)
System.out.println("输入了违法字符，输入错误");
mid = stmp.toString();
if(mid.length() == 0) {
errorflag = false;
System.out.println("输入为空，输入错误");
}
if(!IsNumber(mid.charAt(0))) {
errorflag = false;
System.out.println("输入违法式子，输入错误");
}
//中缀表达式转后缀表达式
post = mid2post(mid).toString();
//后缀表达式求值
output = getResult(post);
if(errorflag) {
System.out.println("输入的中缀表达式为："+mid);
System.out.println("其对应的后缀表达式为："+post);
System.out.println("结果为："+output);
}
System.out.println("是否继续？请输入Y/N");
cont = in.nextLine();
while(!cont.equals("Y") && !cont.equals("N")) {
System.out.println("输入错误，是否继续？请输入Y/N");
cont = in.nextLine();
}
}while(cont.equals("Y"));
in.close();
}
//判断是否是一个数
public static boolean IsNumber(char x) {
if(x == '0' || x == '1' || x == '2' || x == '3' || x == '4' || x == '5' || x == '6' || x == '7' || x == '8' || x == '9')
return true;
else
return false;
}
//判断是否是一个符号
public static boolean IsOperator(char x) {
if(x == '+' || x == '-' || x == '*' || x == '/' || x == '(' || x == ')'|| x == '#'|| x == '.')
return true;
else
return false;
}
//确定符号优先级
public static boolean priority(char x, char y) {
int x1 = 0, y1 = 0;
switch(x) {
case '+': x1 = 1;break;
case '-': x1 = 1;break;
case '*': x1 = 2;break;
case '/': x1 = 2;break;
case '(': x1 = 0;break;
default: x1 = 0;break;
}
switch(y) {
case '+': y1 = 1;break;
case '-': y1 = 1;break;
case '*': y1 = 2;break;
case '/': y1 = 2;break;
case '(': y1 = 3;break;
default: y1 = 0;break;
}
if(x1 >= y1)
return true;
else
return false;
}
//中缀表达式转后缀表达式
public static StringBuffer mid2post(String mid) {
StringBuffer post = new StringBuffer("");
int i = 0;
char ch;
Stack<Character> cs = new Stack<Character>();
cs.push('#');
while(i < mid.length()) {
if(IsNumber(mid.charAt(i))) {
while((mid.charAt(i) >= '0' && mid.charAt(i) <= '9') || mid.charAt(i) == '.') {
post.append(mid.charAt(i));
i++;
if(i == mid.length())
break;
}
post.append(' ');
}
else if(IsOperator(mid.charAt(i))) {
switch(mid.charAt(i)) {
case '(':{
i++;
if(mid.charAt(i) == '-') {
while(mid.charAt(i) != ')') {
post.append(mid.charAt(i));
i++;
}
post.append(' ');
i++;
}else {
i--;
cs.push(mid.charAt(i));
i++;
}
}break;
case ')':{
ch = cs.pop();
do {
post.append(ch);
post.append(' ');
ch = cs.pop();
}while(ch != '(');
i++;
}break;
default:{
while(priority(cs.peek(), mid.charAt(i))) {
post.append(cs.pop());
post.append(' ');
if(cs.peek() == '#')
break;
}
cs.push(mid.charAt(i));
i++;
}break;
}
}else {
System.out.println("输入错误！");
return null;
}
}
while(cs.peek() != '#') {
post.append(cs.pop());
post.append(' ');
}
return post;
}
//后缀表达式求值
public static double getResult(String post) {
double r = new Double(0);
Stack<Double> ds = new Stack<Double>();
int i = 0;
int step = 0; //控制小数的数值转换
double s = 0; //控制整数的数值
double a, b; //b控制小数的数值,a控制整个数的数值
while(i < post.length()) {
if(IsNumber(post.charAt(i))) {
a = 0;
s = 0;
b = 0;
step = 0;
while(IsNumber(post.charAt(i))) {
s = 10*s+post.charAt(i) - 48;
i++;
}
if(post.charAt(i) == '.') {
i++;
while(IsNumber(post.charAt(i))) {
b = 10*b+post.charAt(i) - 48;
i++;
step++;
}
for(int j=0; j<step; j++) {
b /= 10;
}
}
a = s+b;
ds.push(a);
}else if(IsOperator(post.charAt(i)) && post.charAt(i) != '.') {
b = ds.pop();
if(ds.isEmpty()) {
System.out.println("输入错误！");
errorflag = false;
return 0;
}
a = ds.pop();
ds.push(calculate(a, post.charAt(i), b));
i++;
}else {
i++;
}
}
r = ds.pop();
return (r+0);
}
public static double calculate(double a, char t, double b) {
double r = 0;
switch(t) {
case '+': r = a+b; break;
case '-': r = a-b; break;
case '*': r = a*b; break;
case '/': {
if(b == 0) {
errorflag = false;
return 0;
}else {
r = a/b;
break;
}
}
default: {
errorflag = false;
}
}
return r;
}
}
网友评论